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

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]

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]

1	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  ==  []

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

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]

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

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 Comentarios

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.

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.

Responder

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) /= []

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) /= []

Responder

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

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

Responder

La menos conocida de las conjeturas de Goldbach

Soluciones

Otras soluciones

Pensamiento

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Otras soluciones

Pensamiento

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico