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