Clojure入門 - Project Eulerを解いてみる 問１４

第十四問

Collatz数列の話。nが偶数の場合はn/2、奇数の場合は3n+1に続き、最終的にn=1で収束する数列。百万までのnで最長のCollatz数列ができるものを求める。

Collatz数列を簡単に定義するなら以下のようになる。

(defn collatz [n]
  (cond
    (zero? n) []
    (= 1 n)   [1]
    (even? n) (lazy-seq (cons n (collatz (/ n 2))))
    :else     (lazy-seq (cons n (collatz (inc (* 3 n)))))))))

しかし、これはメモ化することでもっと効率的にできる。

(def collatz
  (memoize (fn [n]
             (cond
               (zero? n) []
               (= 1 n)   [1]
               (even? n) (lazy-seq (cons n (collatz (/ n 2))))
               :else     (lazy-seq (cons n (collatz (inc (* 3 n)))))))))

memoizeは確か初利用。結構使い方は簡単である。

(defn count-collatz [n]
  (count (collatz n)))
(apply max-key count-collatz (range 1000000))

あとは組み合わせるだけ。