Project Euler 14

http://projecteuler.net/index.php?section=problems&id=14


コラッツ問題。単に1から100万までの長さを求める。


next_collatz n | (mod n 2) == 1 = 3 * n + 1
| otherwise = div n 2

collatz_length 1 = 1
collatz_length n = 1 + (collatz_length (next_collatz n))
longer (n1,l1) (n2,l2) = if l1 < l2 then (n2,l2) else (n1,l1)
m = 10^6
a = foldr longer (1, 1) (map (\n -> (n, collatz_length(n))) [1..m-1])
main = print(fst(a))

これを実行すると、


*** Exception: stack overflow

関数の入れ子が多すぎるというメッセージに思える。突き詰めると、これでも同じメッセージが出る。


n = 10^6
main = print(foldr max 0 [1..n])

実はfoldrを使わなくてもmaximumという関数があるのでこれを使えばよいが、


main = print(maximum [1..n])

これでも同じことである。
検索したら、http://itpro.nikkeibp.co.jp/article/COLUMN/20070403/267180/?ST=develop&P=1に書いてあって、


import Data.List

n = 10^6
main = print(foldl' max 0 [1..n])

これだと先行評価でメモリを使わないらしい。
しかし、とても遅い。本当は50万以降を調べればよい。その倍の数の方が1つ長いから。また、

4n+1 -> 12n+4 -> 6n+2
2n+1 -> 6n+2
4n+3 -> 12n+10 -> 6n+5

より、6で割って2,4,5余る数は考えなくてよい。


is_valid n = r == 2 || r == 4 || r == 5 where r = mod n 6
a = foldl1' longer (map (\n -> (n, collatz_length(n)))
(filter is_valid [(div m 2)..m-1]))

しかし、この問題は長さを記録していけば、自分より小さくなった時点でもう計算しなくても済むはずである。こういう場合、リストではなく配列を使う。


import Data.Array

a = array (2, 5) [ (n, n * n) | n <- [2..5] ]
main = print(a)

arrayの最初の引数はインデックスの範囲、2番目の引数はインデックスと値のタプルのリスト。


array (2,5) [(2,4),(3,9),(4,16),(5,25)]

と出力される。それぞれの値を出力するには、


main = print(a!5) -- 25

とする。


import Data.Array
import Data.List

next n | mod n 2 == 1 = n * 3 + 1
| otherwise = div n 2
step n max_n | n < max_n = (0, n)
| otherwise = (p + 1, q)
where (p, q) = step (next n) max_n
collatz a 1 = 1
collatz a n = l + a!m
where (l, m) = step n n

m = 10^6
a = array (1, m - 1) [ (n, collatz a n) | n <- [1..m-1] ]
longer (l1, n1) (l2, n2) = if l1 < l2 then (l2, n2) else (l1, n1)
main = print(foldl' longer (0, 0) [ (a!n, n) | n <- [1..m-1] ])