Problem 57 - 連分数で√2

連分数に関する問題。

連分数で√2を求めた時、分子と分母の桁数が違う時の数を数える。

連分数だけじゃ面白くないから、ちょっと変わった感じにしてるみたい。

分数の計算ではまった。

1回目 1 + 1/2
2回目 1 + 1/(2 + 1/2) = 1 + 2/5
3回目 1 + 1/(2 + 2/5) = 1 + 5/12

分子と分母がぐりぐり回る感じになるみたい。

教訓。間違えたなと思った時は、紙に展開してみよう。

(define (problem57 n)
  (letrec ((nod
             (lambda (n) (if (zero? n) 0 (+ 1 (nod (quotient n 10))))))
           (test
             (lambda (n d)
               (let* ((tn (+ n d))
                      (g (gcd tn d)))
                 (if (= (nod (/ tn g)) (nod (/ d g))) 0 1))))
           (iter
             (lambda (i n d acc)
               (if (zero? i)
                   (list (* 1.0 (/ (+ n d) d)) acc)
                   (let ((nn d)
                         (nd (+ (* d 2) n)))
                     (iter (- i 1)
                           nn
                           nd
                           (+ (test nn nd) acc)))))))
    (iter (- n 1) 1 2 0)))

(sqrt 2) ; 1.4142135623730951

(problem57 1) ; (1.5 0)
(problem57 2) ; (1.4 0)
(problem57 3) ; (1.4166666666666667 0)
(problem57 5) ; (1.4166666666666667 0)
(problem57 10) ; (1.4142135516460548 1)
(problem57 20) ; (1.4142135623730947 2)
(problem57 100) ; (1.414213562373095 15)
(problem57 1000) ; (1.414213562373095 153)

だいたい20回位やれば満足できそうな感じ。

全然約分出来てないっぽい感じもするので、gcdを抜いてみたけど、結果は一緒。

gcdする必要はないみたいだ。

√2の連分数して、途中で打ち切ってみた時の分数は互いに素？

連分数 - Wikipedia
ユークリッドの互除法 - Wikipedia

によると、連分数展開は逆gcdしてるようなもんらしい。

逆算してみると、

(modulo 41 29) ; 12
(modulo 29 12) ; 5
(modulo 12 5)  ; 2
(modulo 5 2)   ; 1

(gcd 41 29) ; 1

gcd 1。つまり互いに素。

掛けて足す<->割って余りを出す

ホントだ。

√2は連分数展開を無限に続けるのと同意なので、無理数である。絶対割り切れない。

修正。

(define (problem57 n)
  (letrec ((nod
             (lambda (n) (if (zero? n) 0 (+ 1 (nod (quotient n 10))))))
           (iter
             (lambda (i n d acc)
               (if (zero? i)
                   (list (* 1.0 (/ (+ n d) d)) acc)
                   (let ((nd (+ (* d 2) n)))
                     (iter (- i 1)
                           d
                           nd
                           (+ (if (= (nod (+ d nd)) (nod nd)) 0 1) acc)))))))
    (iter (- n 1) 1 2 0)))

gcdを無くしてスッキリさせてみた。

教訓2。疑問に思った時は深追いせよ。