Números como sumas de primos consecutivos
En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas
|
1 2 |
41 = 2 + 3 + 5 + 7 + 11 + 13 41 = 11 + 13 + 17 |
el 240 se puede escribir de tres formas
|
1 2 3 |
240 = 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 240 = 53 + 59 + 61 + 67 240 = 113 + 127 |
y el 311 se puede escribir de 4 formas
|
1 2 3 4 |
311 = 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 311 = 31 + 37 + 41 + 43 + 47 + 53 + 59 311 = 53 + 59 + 61 + 67 + 71 311 = 101 + 103 + 107 |
Definir la función
|
1 |
sumas :: Integer -> [[Integer]] |
tal que (sumas x) es la lista de las formas de escribir x como suma de dos o más números primos consecutivos. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 |
ghci> sumas 41 [[2,3,5,7,11,13],[11,13,17]] ghci> sumas 240 [[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]] ghci> sumas 311 [[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59], [53,59,61,67,71],[101,103,107]] ghci> maximum [length (sumas n) | n <- [1..600]] 4 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import Data.Numbers.Primes (primes) import Data.List (span) sumas :: Integer -> [[Integer]] sumas x = [ys | n <- takeWhile (< x) primes, let ys = sumaDesde x n, not (null ys)] -- (sumaDesde x n) es la lista de al menos dos números primos -- consecutivos a partir del número primo n cuya suma es x, si existen y -- la lista vacía en caso contrario. Por ejemplo, -- sumaDesde 15 3 == [3,5,7] -- sumaDesde 7 3 == [] sumaDesde :: Integer -> Integer -> [Integer] sumaDesde x n | x == y = take (1 + length us) ys | otherwise = [] where ys = dropWhile (<n) primes (us,y:_) = span (<x) (scanl1 (+) ys) |