Menu Close

La menos conocida de las conjeturas de Goldbach

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

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

  1. 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. 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. 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

Leave a Reply to juaromsan5 Cancel reply

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