Y箱

角谷の予想(コラッツの予想)の問題です。
この問題、中学生ぐらいのころに手計算でノートいっぽいに数字を書いてみたりしてたので、ちょっとなつかしい。

1から逆にたどって系統樹を作ってやればいいかなと思ったんだけど、「途中で百万を超えてもかまわない」という条件があるので、逆にたどるのは戻ってくる可能性を考慮しなければならないということなんだけれど、そこのところがうまく表現できなくて断念。
1から順にしらべることになっちゃいました。

;;
;; Problem 14  : 2011/4/15
;; "Elapsed time: 54894.586881 msecs"

;; momoise : from clojure.org
(defn memoize [f]
  (let [mem (atom {})]
    (fn [& args]
      (if-let [e (find @mem args)]
        (val e)
        (let [ret (apply f args)]
          (swap! mem assoc args ret)
          ret)))))


;; hotpo step count
(defn hotpo-count
  ([n] (hotpo-count n 0))
  ([n count]
     (cond (= n 1) (inc count)
           (even? n) (hotpo-count (/ n 2) (inc count))
           :else     (hotpo-count (+ (* n 3) 1) (inc count)))))

(def hotpo-count (memoize hotpo-count))


(loop [n 1 max-list [0 0]]
  (if (> n 1000000)
    max-list
    (let [hotpo (hotpo-count n)]
      (if (< (nth max-list 1) hotpo)
        (recur (inc n) [n hotpo])
        (recur (inc n) max-list)))))
;;

結局つかわなかった関数

;;
(defn half-or-triple-plus-one [n]
  (if (= n 1) (list 1)
      (let [next-num (if (even? n) (/ n 2) (+ (* n 3) 1))]
        (lazy-seq
         (cons n (half-or-triple-plus-one next-num))))))

(defn hotpo-prev-node
  ([] (rev-ho31 1))
  ([n]
     (let [tpo (/ (- n 1) 3)]
       (if (or (<= tpo 1)
               (not (zero? (mod (- n 1) 3))))
         (list (* n 2))
         (list (* n 2)
               (/ (- n 1) 3))))))

;;