ホーム - Project Euler

Problem 65¶

Convergents of $e$¶

The square root of $2$ can be written as an infinite continued fraction.

$\sqrt{2} = 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + ...}}}}$

The infinite continued fraction can be written, $\sqrt{2} = [1; (2)]$, $(2)$ indicates that $2$ repeats ad infinitum. In a similar way, $\sqrt{23} = [4; (1, 3, 1, 8)]$.

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for $\sqrt{2}$.

$\begin{align} &1 + \dfrac{1}{2} = \dfrac{3}{2} \\ &1 + \dfrac{1}{2 + \dfrac{1}{2}} = \dfrac{7}{5}\\ &1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}} = \dfrac{17}{12}\\ &1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}}} = \dfrac{41}{29} \end{align}$

Hence the sequence of the first ten convergents for $\sqrt{2}$ are:

$1, \dfrac{3}{2}, \dfrac{7}{5}, \dfrac{17}{12}, \dfrac{41}{29}, \dfrac{99}{70}, \dfrac{239}{169}, \dfrac{577}{408}, \dfrac{1393}{985}, \dfrac{3363}{2378}, ...$

What is most surprising is that the important mathematical constant,
$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ... , 1, 2k, 1, ...]$.

The first ten terms in the sequence of convergents for $e$ are:

$2, 3, \dfrac{8}{3}, \dfrac{11}{4}, \dfrac{19}{7}, \dfrac{87}{32}, \dfrac{106}{39}, \dfrac{193}{71}, \dfrac{1264}{465}, \dfrac{1457}{536}, ...$

The sum of digits in the numerator of the $10$^th convergent is $1 + 4 + 5 + 7 = 17$.

Find the sum of digits in the numerator of the $100$^th convergent of the continued fraction for $e$.

$e$ の近似分数¶

2の平方根は無限連分数として書くことができる.

√2 = 1 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + ...))))

無限連分数である √2 = [1;(2)] と書くことができるが, (2) は2が無限に繰り返されることを示す. 同様に, √23 = [4;(1,3,1,8)].

平方根の部分的な連分数の数列から良い有理近似が得られることが分かる.√2の近似分数について考えよう.

1 + 1/2 = 3/2
1 + 1/(2 + 1/2) = 7/5
1 + 1/(2 + 1/(2 + 1/2)) = 17/12
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29

従って, √2の近似分数からなる数列の最初の10項は：

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...

もっとも驚くべきことに, 数学的に重要な定数,

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

e の近似分数からなる数列の最初の10項は：

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...

10項目の近似分数の分子の桁を合計すると1+4+5+7=17である.

e についての連分数である近似分数の100項目の分子の桁の合計を求めよ.

(import (scheme base)
        (gauche base))

(define (continued-fraction lis)
  (let loop ([rest (reverse lis)]
             [result 0])
    (cond
      [(null? rest) result]
      [(zero? result)
       (loop (cdr rest) (car rest))]
      [else
        (loop (cdr rest)
              (+ (car rest)
                 (/ 1 result)))])))

(define e-generator
  (let ([index 0] [current-center 2])
    (^[]
      (let ([next-index (mod (+ index 1) 3)])
        (ecase index
          [(0 2)
           (set! index next-index)
           1]
          [(1)
           (set! index next-index)
           (let ([return-value current-center])
             (set! current-center (+ current-center 2))
             return-value)])))))

(define e-list
  (generator->lseq 2 e-generator))

(define (number->list num)
  (assume (exact-integer? num))
  (assume (not (negative? num)))
  (if (zero? num)
    '(0)
    (let loop ([rest num] [current '()])
      (if (zero? rest)
        current
        (loop (div rest 10)
              (cons (mod rest 10)
                    current))))))

(define answer-65
  (apply +
         (number->list
           (numerator
             (continued-fraction
               (take e-list 100))))))

(format #t "65: ~d~%" answer-65)