http://projecteuler.net/index.php?section=problems&id=14
コラッツ問題。単に1から100万までの長さを求める。
next_collatz n | (mod n 2) == 1 = 3 * n + 1
| otherwise = div n 2collatz_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.Listn = 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.Arraya = 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.Listnext 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 nm = 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] ])