Menu Close

La menos conocida de las conjeturas de Goldbach

José A. Alonso,

Goldbach, el de la famosa conjetura, hizo por lo menos otra conjetura que finalmente resultó ser falsa.

Esta última decía que todo número compuesto impar puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Así por ejemplo,

    9 =  7 + 2×1^2
   15 =  7 + 2×2^2
   21 =  3 + 2×3^2
   25 =  7 + 2×3^2
   27 = 19 + 2×2^2
   33 = 31 + 2×1^2

Definir las sucesiones

   imparesCompuestos :: [Integer]
   descomposiciones :: Integer -> [(Integer,Integer)]
   contraejemplosGoldbach :: [Integer]

tales que

  • imparesCompuestos es la lista de los números impares compuestos. Por ejemplo,
     take 9 imparesCompuestos  ==  [9,15,21,25,27,33,35,39,45]
  • (descomposiciones n) es la lista de las descomposiciones de n de n como la suma de un número primo más dos veces la suma de un cuadrado. Por ejemplo, 
     descomposiciones 9     ==  [(7,1)]
     descomposiciones 21    ==  [(3,9),(13,4),(19,1)]
     descomposiciones 5777  ==  []

Las 3 descomposiciones de 21 son

     21 =  3 + 2*9 = 21 + 2*3^2
     21 = 13 + 2*4 = 13 + 2*3^2
     21 = 19 + 2*1 = 19 + 2*1^2
  • contraejemplosGoldbach es la lista de los contraejemplos de la anterior conjetura de Goldbach; es decir, los números impares compuestos que no pueden expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Por ejemplo,
   take 2 contraejemplosGoldbach  ==  [5777,5993]

Comprobar con QuickCheck que la conjetura de Golbach se verifica a partir de 5993; es decir, todo número compuesto impar mayor que 5993 puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado.

Nota: Basado en el artículo La menos conocida de las conjeturas de Goldbach de Claudio Meller en el blog Números y algo más.

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck
 
imparesCompuestos :: [Integer]
imparesCompuestos = filter esCompuesto [3,5..]
 
-- (esCompuesto x) se verifica si x es un número compuesto. Por ejemplo,
--    esCompuesto 6  ==  True
--    esCompuesto 7  ==  False
esCompuesto :: Integer -> Bool
esCompuesto = not . isPrime
 
contraejemplosGoldbach :: [Integer]
contraejemplosGoldbach = filter esContraejemplo imparesCompuestos
 
-- (esContraejemplo x) es verifica si el número impar compuesto x es un
-- contraejemplo de la conjetura de Goldbach. Por ejemplo,
--    esContraejemplo 5777  ==  True
--    esContraejemplo 15    ==  False
esContraejemplo :: Integer -> Bool
esContraejemplo = null . descomposiciones
 
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n =
  [(p,x) | p <- takeWhile (<=n) primes
         , (n - p) `mod` 2 == 0
         , let x = (n - p) `div` 2
         , esCuadrado x]
 
-- (esCuadrado x) es verifica si x es un cuadrado perfecto. Por ejemplo, 
--    esCuadrado 16  ==  True
--    esCuadrado 27  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = y^2 == x
  where y = ceiling (sqrt (fromIntegral x))
 
-- La propiedad es
prop_conjetura :: Int -> Property
prop_conjetura n =
  n >= 0 ==> not (esContraejemplo (imparesCompuestosMayore5993 !! n))
  where imparesCompuestosMayore5993 = dropWhile (<=5993) imparesCompuestos
 
-- La comprobación es
--    λ> quickCheck prop_conjetura
--    +++ 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>

Pensamiento

“Obvio es la palabra más peligrosa de las matemáticas.”

Eric Temple Bell

Medio
, , , , , , , , , , , , , ,

3 soluciones de “La menos conocida de las conjeturas de Goldbach”

  1. Responder
    fercarnav 
    import Test.QuickCheck
import Data.List
import Data.Numbers.Primes
 
imparesCompuestos :: [Integer]
imparesCompuestos = [2*x +1 | x <- [1..], not (isPrime (2*x + 1))]
 
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n =
  [(x,div (n-x) 2) | x <- takeWhile (<n) primes
                   , mod (n-x) 2 == 0
                   , esCuadrado (div (n-x) 2) ]
 
esCuadrado :: Integer -> Bool
esCuadrado n = n == last (takeWhile (<=n) cuadrados)
 
cuadrados :: [Integer]
cuadrados = [x^2 | x <- [1..]]
 
contraejemplosGoldbach :: [Integer]
contraejemplosGoldbach =
  [ x | x <- imparesCompuestos
      , descomposiciones x == []]
 
prop_descomposiciones :: Integer -> Property
prop_descomposiciones x =
  not (isPrime (2*(abs x) + 5995)) ==>
  descomposiciones (2*(abs x) + 5995) /= []
 
-- λ> quickCheck prop_descomposiciones
-- +++ OK, passed 100 tests.
  2. Responder
    juaromsan5 
    import Data.Numbers.Primes
import Data.List
 
imparesCompuestos :: [Integer]
imparesCompuestos = [x | x <- [3,5..], not (isPrime x)]
 
descomposiciones :: Integer -> [(Integer, Integer)]
descomposiciones x =
  [(a,b) | a <- takeWhile (<x) primes
         , b <- takeWhile (<(x-1)) cuadradosdeEnteros
         , a + 2*b == x]
 
cuadradosdeEnteros :: [Integer]
cuadradosdeEnteros = [y^2 | y <- [1..]] 
 
contraejemplosGoldbach :: [Integer]
contraejemplosGoldbach =
  [z | z <-imparesCompuestos
     , descomposiciones z == []]
 
prop_descomposiciones :: Integer -> Property
prop_descomposiciones x =
  not (isPrime (2*(abs x) + 5995)) ==>
  descomposiciones (2*(abs x) + 5995) /= []
  3. Responder
    Carlos 
    import Test.QuickCheck
import Data.Numbers.Primes
import Data.Ord
 
imparesCompuestos :: [Integer]
imparesCompuestos = minus [3,5..] primes
  where
    minus (x:xs) (y:ys) = case (compare x y) of 
                          LT -> x : minus  xs  (y:ys)
                          EQ ->     minus  xs     ys 
                          GT ->     minus (x:xs)  ys
    minus  xs     _     = xs
 
isqrt :: Integer -> Integer
isqrt 0 = 0
isqrt 1 = 1
isqrt n = head $ dropWhile stop $ iterate step (div n 2)
  where step x = div (x + div n x) 2
        stop x = x^2 > n
 
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n = [(x,i) | x <- takeWhile (<n) (tail primes)
                            , let i = div (n-x) 2
                            , isqrt i^2 == i]
 
contraejemplosGoldbach :: [Integer]
contraejemplosGoldbach = filter (null . descomposiciones) imparesCompuestos
 
imparesCompuestos5993 :: [Integer]
imparesCompuestos5993 = dropWhile (<5993) imparesCompuestos
 
prop_Goldbach :: (Positive Int) -> Property
prop_Goldbach (Positive k) = not (null (descomposiciones n)) === True
                            where n = imparesCompuestos5993 !! k
 
main = quickCheck prop_Goldbach

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.