Ir al contenido principal

Sumas de 4 primos

La conjetura de Waring sobre los números primos establece que todo número impar es primo o la suma de tres primos. La conjetura de Goldbach afirma que todo número par mayor que 2 es la suma de dos números primos. Ambos problemas ha estado abiertos durante más de 200 años. En este problema no se propone su solución, sino una tarea más simple: buscar una manera de expresar los enteros mayores que 7 como suma de exactamente cuatro números primos; es decir, definir la función

suma4primos :: Integer -> (Integer,Integer,Integer,Integer)

tal que (suma4primos n) es una cuádrupla (a,b,c,d) de números primos cuya suma es n (que se supone mayor que 7). Por ejemplo,

suma4primos 24             ==  (2,2,3,17)
suma4primos 1234567890123  ==  (2,3,29,1234567890089)

Comprobar con QuickCheck que suma4primos es correcta; es decir si (suma4primos n) es (a,b,c,d) entonces los números a, b c y d son primos y su suma es n.

Nota: Para cada n pueden existir distintas cuádruplas que cumplan la especificación. Por ejemplo, para el 16 hay tres: (2,2,5,7), (3,3,3,7) y (3,3,5,5). Cualquiera de ellas se admite como solución.

Soluciones

import Data.Numbers.Primes (isPrime, primes)
import Test.QuickCheck

-- 1ª solución
-- ===========

suma4primos1 :: Integer -> (Integer, Integer, Integer, Integer)
suma4primos1 n =
    head[(a,b,c,d) | let as = takeWhile (<n) primes,
                     a <- as,
                     let bs = takeWhile (<n-a) as,
                     b <- bs,
                     let cs = takeWhile (<n-a-b) bs,
                     c <- cs,
                     let d = n-a-b-c,
                     isPrime d]

-- 2ª solución
-- ===========

suma4primos2 :: Integer -> (Integer,Integer,Integer,Integer)
suma4primos2 n | even n    = (2,2,a,b)
               | otherwise = (2,3,c,d)
               where (a,b) = head (sumas2primos (n-4))
                     (c,d) = head (sumas2primos (n-5))

sumas2primos :: Integer -> [(Integer,Integer)]
sumas2primos n = [(x,y) | x <- takeWhile (<n) primes,
                          let y = n-x,
                          x <= y,
                          isPrime y]

-- Verificación                                                     --
-- ============

-- La propiedad es
prop_suma4primos :: Integer -> Property
prop_suma4primos n =
    n > 7 ==> a+b+c+d == n && all isPrime [a,b,c,d]
    where (a,b,c,d) = suma4primos2 n

-- La comprobación es
--    λ> quickCheck prop_suma4primos
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia                                        --
-- =========================

-- La comparación es
--    λ> suma4primos1 10000000
--    (2,2,5,9999991)
--    (9.66 secs, 4346086952 bytes)
--
--    λ> suma4primos2 10000000
--    (2,2,5,9999991)
--    (0.01 secs, 2099888 bytes)