Project Euler #014 – コラッツの問題

9 1月 2010

Project EulerをClojureでおさらいシリーズ。
Problem 14

日本語訳：

正の整数に対して次のように繰り返す数列を定義する。

n → n/2 （nが偶空の場合） n → 3n + 1 （nが奇数の場合）

この規則に沿って 13からはじめると、次の数列を生成する。

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

13からはじまり1でおわる10項の数列とみることができる。
どの数からはじめても最終的には１になると考えられているがまだ証明はされていない。（コラッツの問題）

100万未満のどの数からスタートすれば最も長い数列を得られるかを求めよ。

注意：途中の項の数字が100万を越えてもかまわない。

計算の重複によるムダをいかに少なくするかがカギかな。

Nに対する数列の長さは再帰的に求めて、その値をキャッシュするのがよさげ。

以前Rubyで解いたバージョンはこちら：

#!/usr/bin/env ruby
 
def next_collatz(n)
  return 1 if n == 1
  return n / 2 if n.even?
  3 * n + 1
end
 
def get_chains_num(n)
  c = 1
  until n == 1
    n = next_collatz(n)
    c += 1
  end
  c
end
 
def (Chains = [0, 1]).[](n)
  return super if super
  if n < 2_000_000
    return Chains[n] = Chains[next_collatz(n)] + 1
  else 
    return get_chains_num(n)
  end
end
 
max = 0
point = 1
1.upto(1_000_000 - 1).each do |n|
  val = Chains[n]
  if val > max
    max = val 
    point = n
  end
end
 
p "At #{point} : chain length = #{max}"

Project Euler #002 のときと同様に配列の特異メソッドとして定義することで、Nに対するコラッツ数の長さの値をキャッシュしています。

これが意外と速い。
ruby1.9系だと20秒かかりませんでした。

さて、Clojureで書いてみます。

(ns euler.p014)
 
(defn collatz-length
  "Return chain length of Collatz sequence of N."
  [n]
  (cond (= n 1) 1
	(even? n) (inc (collatz-length (/ n 2)))
	:else (inc (collatz-length (inc (* 3 n))))))
 
(defn memoize-under
  "Apply memoize when arg is under limit."
  [limit f]
  (let [mem (atom {})]
    (fn [arg]
      (if (> arg limit)
	(f arg)
	(if-let [e (find @mem arg)]
	  (val e)
	  (let [ret (f arg)]
	    (swap! mem assoc arg ret)
	    ret))))))
 
(def collatz-length (memoize-under 400000 collatz-length))
 
(defn pick-grater-last
  "Pick coll of which last value is greater."
  [coll-1 coll-2]
  (if (> (last coll-1)
	 (last coll-2))
    coll-1
    coll-2))
 
(println "Answer : "
	 (first
	  (reduce pick-grater-last
		  (map #(vector % (collatz-length %))
		       (range 1 1000000)))))