Números como sumas de primos consecutivos.
El número 311 se puede escribir de 5 formas distintas como suma de 1 o más primos consecutivos
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 311 = 311
el número 41 se puede escribir de 4 formas
41 = 2 + 3 + 5 + 7 + 11 + 13 41 = 11 + 13 + 17 41 = 41
y el número 14 no se puede escribir como suma de primos consecutivos.
Definir la función
sumas :: Integer -> [[Integer]]
tal que (sumas x) es la lista de las formas de escribir x como suma de uno o más números primos consecutivos. Por ejemplo,
λ> 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],[311]] λ> sumas 41 [[2,3,5,7,11,13],[11,13,17],[41]] λ> sumas 14 [] λ> [length (sumas n) | n <- [0..20]] [0,0,1,1,0,2,0,1,1,0,1,1,1,1,0,1,0,2,1,1,0] λ> maximum [length (sumas n) | n <- [1..600]] 5
Soluciones
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)