Sumas de dos primos
Definir la sucesión
sumasDeDosPrimos :: [Integer]
cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,
λ> take 23 sumasDeDosPrimos [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31] λ> sumasDeDosPrimos4 !! (5*10^4) 83674
Soluciones
import Data.Numbers.Primes (isPrime, primes) -- 1ª definición -- ============= sumasDeDosPrimos1 :: [Integer] sumasDeDosPrimos1 = [n | n <- [1..], not (null (sumaDeDosPrimos1 n))] -- (sumasDeDosPrimos1 n) es la lista de pares de primos cuya suma es -- n. Por ejemplo, -- sumaDeDosPrimos 9 == [(2,7),(7,2)] -- sumaDeDosPrimos 16 == [(3,13),(5,11),(11,5),(13,3)] -- sumaDeDosPrimos 17 == [] sumaDeDosPrimos1 :: Integer -> [(Integer,Integer)] sumaDeDosPrimos1 n = [(x,n-x) | x <- primosN, isPrime (n-x)] where primosN = takeWhile (< n) primes -- 2ª definición -- ============= sumasDeDosPrimos2 :: [Integer] sumasDeDosPrimos2 = [n | n <- [1..], not (null (sumaDeDosPrimos2 n))] -- (sumasDeDosPrimos2 n) es la lista de pares (x,y) de primos cuya suma -- es n y tales que x <= y. Por ejemplo, -- sumaDeDosPrimos2 9 == [(2,7)] -- sumaDeDosPrimos2 16 == [(3,13),(5,11)] -- sumaDeDosPrimos2 17 == [] sumaDeDosPrimos2 :: Integer -> [(Integer,Integer)] sumaDeDosPrimos2 n = [(x,n-x) | x <- primosN, isPrime (n-x)] where primosN = takeWhile (<= (n `div` 2)) primes -- 3ª definición -- ============= sumasDeDosPrimos3 :: [Integer] sumasDeDosPrimos3 = filter esSumaDeDosPrimos3 [4..] -- (esSumaDeDosPrimos3 n) se verifica si n es suma de dos primos. Por -- ejemplo, -- esSumaDeDosPrimos3 9 == True -- esSumaDeDosPrimos3 16 == True -- esSumaDeDosPrimos3 17 == False esSumaDeDosPrimos3 :: Integer -> Bool esSumaDeDosPrimos3 n | odd n = isPrime (n-2) | otherwise = any isPrime [n-x | x <- takeWhile (<= (n `div` 2)) primes] -- 4ª definición -- ============= -- Usando la conjetura de Goldbach que dice que "Todo número par mayor -- que 2 puede escribirse como suma de dos números primos" . sumasDeDosPrimos4 :: [Integer] sumasDeDosPrimos4 = filter esSumaDeDosPrimos4 [4..] -- (esSumaDeDosPrimos4 n) se verifica si n es suma de dos primos. Por -- ejemplo, -- esSumaDeDosPrimos4 9 == True -- esSumaDeDosPrimos4 16 == True -- esSumaDeDosPrimos4 17 == False esSumaDeDosPrimos4 :: Integer -> Bool esSumaDeDosPrimos4 n = even n || isPrime (n-2) -- Comparación de eficiencia -- ========================= -- λ> sumasDeDosPrimos1 !! 3000 -- 4731 -- (6.66 secs, 3,278,830,304 bytes) -- λ> sumasDeDosPrimos2 !! 3000 -- 4731 -- (3.69 secs, 1,873,984,088 bytes) -- λ> sumasDeDosPrimos3 !! 3000 -- 4731 -- (0.35 secs, 175,974,016 bytes) -- λ> sumasDeDosPrimos4 !! 3000 -- 4731 -- (0.07 secs, 18,396,432 bytes) -- -- λ> sumasDeDosPrimos3 !! 30000 -- 49785 -- (6.65 secs, 3,785,736,416 bytes) -- λ> sumasDeDosPrimos4 !! 30000 -- 49785 -- (1.06 secs, 590,767,736 bytes)
Referencia
- N.J.A. Sloane, Sucesión A014091 en OEIS.