project euler problem 12

三角数の数列は自然数の和で表わされ、7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である。 三角数の最初の10項は

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる。

最初の7項について、その約数を列挙すると、以下のとおり。

?1: 1

?3: 1,3

?6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

これから、7番目の三角数である28は、6個以上の約数をもつ最初の三角数であることが分る。

では、501 個以上の約数をもつ最初の三角数はいくらか。

素因数分解だ。またかよ。なぜか素数周りはいやなイメージが…がんばるか。

約数の数は素因数分解の指数＋１の積で表せるので

import List
main=print$problem
problem= head  $ dropWhile (\x->snd x<501) $ map (\x->(x,divisor x)) $ trinum

trinum:: [Int]
trinum  = [div (n*(n+1)) 2|n<-[1..]]

factorize::Int -> [Int]
factorize x = f x 2 []
    where f x y xs = if x<y then xs else if mod x y==0 then f (div x y) y (y:xs) else f x (y+1) xs

divisor::Int -> Int
divisor x = foldl (\a b->a*(length b+1)) 1 $ group $ factorize x

素直に書いてみた。

$ time /usr/bin/runghc 12.hs
(76576500,576)

real:1m18.970s,user:1m18.825s,sys:0m0.140s

さすがにコンパイルしないと答えが返ってくるのが遅い。emacsでやってるメリットがないｗ

$ time ./a.out
(76576500,576)

real:0m4.851s,user:0m4.840s,sys:0m0.008s

5秒か、悪くない。

他の人の解法。なかなかおもしろい。
http://tsumuji.cocolog-nifty.com/tsumuji/2010/01/project-euler-2.html