Question

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

$$\sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{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{aligned} 1 + \frac{1}{2} & = \frac{3}{2} \\ 1 + \frac{1}{2 + \frac{1}{2}} & = \frac{7}{5} \\ 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} & = \frac{17}{12} \\ 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}}} & = \frac{41}{29} \end{aligned}$$

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

$$1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}, \frac{1393}{985}, \frac{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, \frac{8}{3}, \frac{11}{4}, \frac{19}{7}, \frac{87}{32}, \frac{106}{39}, \frac{193}{71}, \frac{1264}{465}, \frac{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$.

Haskell

convergents :: [Integer]
convergents = 2 : concat [[1, 2*k, 1] | k <- [1..]]

rationalize :: [Integer] -> (Integer, Integer)
rationalize = foldr (\x (n, d) -> (x*n + d, n)) (1, 0)

digits :: Integer -> [Integer]
digits 0 = []
digits n = r : digits q
    where (q, r) = quotRem n 10

main :: IO ()
main = print $ sum $ digits $ fst $ rationalize $ take 100 convergents

$ ghc -O2 -o e-convergents e-convergents.hs
$ time ./e-convergents
real   0m0.002s
user   0m0.000s
sys    0m0.002s

Python

#!/usr/bin/env python
from itertools import islice

def take(iterable, n):
    return list(islice(iterable, n))

def e():
    yield 2
    k = 1
    while True:
        yield 1
        yield 2*k
        yield 1
        k += 1

def rationalize(frac):
    if len(frac) == 0:
        return (1, 0)
    elif len(frac) == 1:
        return (frac[0], 1)
    else:
        remainder = frac[1:len(frac)]
        (num, denom) = rationalize(remainder)
        return (frac[0] * num + denom, num)

numerator = rationalize(take(e(), 100))[0]
print(sum(int(d) for d in str(numerator)))

$ time python3 continued.py
real   0m0.017s
user   0m0.017s
sys    0m0.000s