problem 57 - mtsuyuguの日記

2 の平方根を連分数で近似するとき、 1000 段までの近似値のなかで、分子の桁数が分母の桁数より多いものはいくつあるかという問題です。

初めは桁数を求めるために

(floor (+ 1 (/ (log n) (log 10)))

としてましたが、n = 1000 のとき演算誤差のために (/ (log 1000) (log 10)) が 2.99999... になってしまい全ての場合で正しい桁数が得られないことが分かったので、10 で割っていく方法にしました。

(use srfi-1)

(define root2
  (let ((r '())) ; lookup-table for memomization
    (define (root-2-iter n)
      (let1 found (assq n r)
            (cond ((= n 0) (/ 1 2))
                  (found (cdr found))
                  (else
                    (let1 v (/ 1 (+ 2 (root-2-iter (- n 1))))
                          (set! r (acons n v r))
                          v)))))
    (compose (pa$ + 1) root-2-iter)))

(define (keta n)
  (let loop ((n n) (i 0))
    (if (= n 0) i
      (loop (quotient n 10) (+ i 1)))))

(define (p57)
  (count (lambda (x)
           (let* ((r2 (root2 x))
                  (n (keta (numerator r2)))
                  (d (keta (denominator r2))))
             (> n d))) (iota 1000)))

(print (p57))

分かったこと

numerator, denominator で有理数のそれぞれ分子、分母を得ることができる。