Problem 65 - eの連分数

翻訳無いけどやってみる。

Problem 65 - Project Euler

√2の連分数は、

√2 = [1;(2)]

と表せて、

eの連分数表記は、

e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]

こんなんらしい。100項目の分子の数値の和を求める。

問題は長いけど、やることはシンプル。

前にも連分数が出てきたけど、今回は(1,2k,1)というちょっと変則的な連分数なので、再帰で下の方から求めていく。

連分数リストなら何でも来い的な感じに仕上げてみた。

(define (problem65 seed sequence)
  (let ((res (fold-right
               (lambda (n acc)
                 (cons (cdr acc)
                       (if (zero? n)
                           n
                           (+ (* (cdr acc) n) (car acc)))))
               '(0 . 1)
               sequence)))
    (cons (+ (car res) (* seed (cdr res)))
          (cdr res))))

(define (make-e-sequence n)
  (take
    (fold-right (lambda (n acc)
                (cons* 1 (* n 2) 1 acc))
              '()
              (iota (+ (quotient n 3) 1) 1))
    (- n 1)))


(apply + (number->list (car (problem65 2 (make-e-sequence 10))))) ; 17
(apply + (number->list (car (problem65 2 (make-e-sequence 100))))) ; 272

無限リストが欲しくなる問題だけど、無限リストの作り方がイマイチわかんね。

number->listは略。