# Project Euler Problem 65 Solution

## 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$.

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