It is possible to write ten as the sum of primes in exactly five different ways:
What is the first value which can be written as the sum of primes in over five thousand different ways?
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.010s user 0m0.008s sys 0m0.000s