日: 2008年3月11日

cf. Way of My Life – コラッツ予想

Haskell と OCaml でやってみた。
与えられた数から1になるまでをリストで返す。

collatz :: Int -> [Int]
collatz 1 = 1 : []
collatz n | n `mod` 2 == 0 = n : collatz (n `div` 2)
          | otherwise = n : collatz (n * 3 + 1)

*Main> collatz 19
[19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

割り算には値を整数で返す div を使っている。はじめ / を使ったら型があわずにエラーになった。

今度は OCaml 版。やってることはおんなじ。

let rec collatz = function
    1 -> 1 :: []
    | n when n mod 2 = 0 -> n :: collatz (n / 2)
    | n -> n :: collatz (n * 3 + 1)

# collatz 19;;
- : int list =
[19; 58; 29; 88; 44; 22; 11; 34; 17; 52; 26; 13; 40; 20; 10; 5; 16; 8; 4; 2; 1]