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