Problem14(1) - 力づく

OCaml 30分プログラム

30分プログラム、その277。3n+1問題 via Project Euler。

正の整数に以下の式で繰り返し生成する数列を定義する。

n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる。

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる。 この数列はどのような数字からはじめても最終的には 1 になると考えられているが、まだそのことは証明されていない(コラッツ問題)

さて、100万未満の数字の中でどの数字からはじめれば一番長い数列を生成するか。

注意: 数列の途中で100万以上になる可能性もある

とりあえず、力づくでチェレンジ。最近、覚えたunfoldを使ってみた。が、残念ながら遅すぎたので断念した。続きはまた明日。

使い方

# solve ();;
....

ソースコード

let ($) f g x = f (g x)
let (@@) f g = f g

let rec unfold f b = 
  match f b with
      Some (a,b') -> a :: unfold f b'
    | _ -> []

let even n = (n mod 2) = 0

let collatz n =
  let f = 
    function 1 -> None
           | n -> 
	       if even n 
	         then Some (n,n/2)
	         else Some (n,3*n+1) 
  in
    unfold f n

let range a b = 
  let rec f r a b = 
    if a = b 
      then r
      else f (a::r) (a+1) b
  in
    f [] a b

let solve _ =
  let xs = List.rev_map (List.length $ collatz) @@ range 1 1_000_000 in
    List.fold_left max 0 xs

参考