Máximos locales en los números de descomposiciones de Goldbach
La conjetura de Goldbach afirma que todo número entero mayor que 2 se puede expresar como suma de dos primos.
Las descomposiciones de Goldbach son las maneras de expresar un número como suma de dos primos. Por ejemplo, el número 10 tiene dos descomposiciones de Goldbach ya que se puede expresar como la suma de 3 y 7 y la suma de 5 y 5.
Definir las funciones
|
1 2 3 |
descomposicionesGoldbach :: Integer -> [(Integer,Integer)] numeroGoldbach :: Integer -> Integer tieneMaximoLocalGoldbach :: Integer -> Bool |
tales que
- (descomposicionesGoldbach n) es la lista de las descomposiciones de Goldbach del número n. Por ejemplo,
|
1 2 3 4 5 6 |
descomposicionesGoldbach 5 == [(2,3)] descomposicionesGoldbach 10 == [(3,7),(5,5)] descomposicionesGoldbach 22 == [(3,19),(5,17),(11,11)] descomposicionesGoldbach 34 == [(3,31),(5,29),(11,23),(17,17)] descomposicionesGoldbach 35 == [] descomposicionesGoldbach (9+10^9) == [(2,1000000007)] |
- (numeroGolbach n) es el número de descomposiciones de Goldbach del número n. Por ejemplo,
|
1 2 3 4 5 6 7 |
numeroGoldbach 5 == 1 numeroGoldbach 10 == 2 numeroGoldbach 22 == 3 numeroGoldbach 34 == 4 numeroGoldbach 35 == 0 numeroGoldbach (9+10^9) == 1 maximum [numeroGoldbach n | n <- [2..3000]] == 128 |
- (tieneMaximoLocalGoldbach n) se verifica si en n se alcanza un máximo local en el número de descomposiciones de Goldbach; es decir, los números n tales que el número de descomposiciones de Goldbach de n es mayor o igual que las de n-1 y las de n+1. Por ejemplo,
|
1 2 |
λ> filter tieneMaximoLocalGoldbach [1..45] [1,2,4,5,6,7,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44] |
En el ejemplo anterior se comprueba que en los múltiplos de 6 (es decir, en 6, 12, 18, 24, 30, 36 y 42), el número de descomposiciones de Goldbach alcanza un máximo local. Comprobar con QuickCheck que esta propiedad se cumple en general; es decir, para todo entero positivo n, el número de descomposiciones de Goldbach en 6n es un máximo local.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
import Data.List (genericLength) import Data.Numbers.Primes (primes, isPrime) import Test.QuickCheck -- Definiciones de descomposicionesGoldbach -- ======================================== -- 1ª definición descomposicionesGoldbach1 :: Integer -> [(Integer,Integer)] descomposicionesGoldbach1 n = [(p,n-p) | p <- takeWhile (<= n `div` 2) primes , isPrime (n-p)] -- 2ª definición descomposicionesGoldbach2 :: Integer -> [(Integer,Integer)] descomposicionesGoldbach2 n | odd n = [(2,n-2) | isPrime (n-2)] | otherwise = [(p,n-p) | p <- takeWhile (<= n `div` 2) primes , isPrime (n-p)] -- Comparación de eficiencia -- λ> descomposicionesGoldbach1 (9+10^8) -- [(2,100000007)] -- (10.75 secs, 32,177,389,480 bytes) -- λ> descomposicionesGoldbach2 (9+10^8) -- [(2,100000007)] -- (0.01 secs, 3,228,912 bytes) -- En lo que sigue, usaremos la 2ª definición descomposicionesGoldbach :: Integer -> [(Integer,Integer)] descomposicionesGoldbach = descomposicionesGoldbach2 -- Definición de numeroGolbach -- =========================== numeroGoldbach :: Integer -> Integer numeroGoldbach = genericLength . descomposicionesGoldbach -- Definición de tieneMaximoLocalGoldbach -- ====================================== tieneMaximoLocalGoldbach :: Integer -> Bool tieneMaximoLocalGoldbach n = numeroGoldbach (n-1) <= x && x >= numeroGoldbach (n+1) where x = numeroGoldbach n -- La propiedad es prop_Goldbach :: Integer -> Property prop_Goldbach n = n > 0 ==> tieneMaximoLocalGoldbach (6*n) -- La comprobación es -- λ> quickCheck prop_Goldbach -- +++ OK, passed 100 tests. |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Referencia
- Local maxima of number of Goldbach decompositions en ProofWiki.
- Sucesión A061358 de OEIS.
Pensamiento
Te abanicaras
con un madrigal que diga:
en amor el olvido pone la sal.Antonio Machado
2 Comentarios