Question
It is possible to write ten as the sum of primes in exactly five different ways:
\begin{aligned} &7 + 3 \\ &5 + 5 \\ &5 + 3 + 2 \\ &3 + 3 + 2 + 2 \\ &2 + 2 + 2 + 2 + 2 \end{aligned}
What is the first value which can be written as the sum of primes in over five thousand different ways?
Haskell
primes :: [Int]
primes = 2 : sieve primes [3,5..] where
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
where (h, t) = span (< p*p) xs
primePartition :: Int -> Int
primePartition = p primes where
p _ 0 = 1
p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
main :: IO ()
main = print $ fst $ head $ dropWhile ((<= 5000) . snd) [(n, primePartition n) | n <- [1..]]$ ghc -O2 -o prime-summations prime-summations.hs
$ time ./prime-summations
real 0m0.007s
user 0m0.007s
sys 0m0.000s