７８問目

http://projecteuler.net/index.php?section=problems&id=78
n 個のコインをいくつかの山に分けるときの場合の数を p(n) とおく。例えば 5 個のコインは 7 通りの方法で分けられるので p(5)=7 である。p(n) が百万の倍数となるような n のうち最も小さい値を求める。
真正面から解こうとすると何年経っても終わらないので、７６問目のフォーラムを見て、Euler の Partition Function （分割関数）のお世話になりました。
これだけ対象の数字が大きくなると List では力不足なので、Array に初挑戦。
List だと 30 分、Array だと 10 秒といったところです。

import Data.Array

main = print $ euler078 1000000

euler078 :: Integer -> Int
euler078 m = head $ filter (\ n -> (mod (parts ! n) m) == 0) [1..]

parts :: Array Int Integer
parts = listArray (0, 1000000) (1 : map part [1..1000000])

part :: Int -> Integer
part n = sum [ s * (parts ! (n - p)) | (p, s) <- takeWhile ((n >=) . fst) penta ]

penta :: [(Int, Integer)]
penta = zip (concat $ zipWith (\ a b -> [a, b]) (scanl1 (+) [1,4..]) (scanl1 (+) [2,5..])) (cycle [1,1,-1,-1])