Y箱

2の平方根の連分数を1000段まで順に展開したときの分数表現の分子の桁数がが分母の桁数を超えるのは何回あるかっていう問題。

連分数の展開には一般項の公式があるのでそれをあてはめて計算。

と、ここで、分母と分子の式が漸化式になっているんだが、大きくなるとメモリが足りなくなるので、memoizeを使ってメモ化したのだか効果なし。
なんでだーって調べて分ったのがちょっと前のポスト。

defn-memoを使って再定義したらちゃんとできた。

;;
;; Problem 57  : 2011/6/21
;; "Elapsed time: 4859.538293 msecs"
(defn cf-seq [n]
  (if (zero? n)
    1
    2))

(defn cf-numerator [n]
  (cond (zero? n) 1
        (= 1 n) (cf-seq 0)
        :else (+ (* (cf-seq (dec n))
                    (cf-numerator (dec n))) 
                 (cf-numerator (- n 2)))))

(defn cf-denominator [n]
  (cond (zero? n) 0
        (= 1 n) 1
        :else (+ (* (cf-seq (dec n))
                    (cf-denominator (dec n))) 
                 (cf-denominator (- n 2)))))

(def cf-numerator (memoize cf-numerator))
(def cf-denominator (memoize cf-denominator))

;;

memoizeじゃあだめ。計算おわらない。

;;
(defn-memo cf-numerator [n]
  (cond (zero? n) 1
        (= 1 n) (cf-seq 0)
        :else (+ (* (cf-seq (dec n))
                    (cf-numerator (dec n))) 
                 (cf-numerator (- n 2)))))

(defn-memo cf-denominator [n]
  (cond (zero? n) 0
        (= 1 n) 1
        :else (+ (* (cf-seq (dec n))
                    (cf-denominator (dec n))) 
                 (cf-denominator (- n 2)))))


(defn pe57? [n]
  (> (count (num-to-list (cf-numerator n)))
     (count (num-to-list (cf-denominator n)))))


(count (filter true? (pmap pe57? (range 1000))))
;;