Project Euler Problem 65 Solution

Question

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

2=1+12+12+12+12+12+...\displaystyle \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, 2=[1;(2)]\sqrt{2} = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, 23=[4;(1,3,1,8)]\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 2\sqrt{2}.

1+12=321+12+12=751+12+12+12=17121+12+12+12+12=4129\displaystyle \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 2\sqrt{2} are:

1,32,75,1712,4129,9970,239169,577408,1393985,33632378,...\displaystyle 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,...]e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

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

2,3,83,114,197,8732,10639,19371,1264465,1457536,...\displaystyle 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 10th10^{th} convergent is 1+4+5+7=171+4+5+7=17.

Find the sum of digits in the numerator of the 100th100^{th} convergent of the continued fraction for ee.

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.001s
user   0m0.000s
sys    0m0.000s

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.020s
user   0m0.016s
sys    0m0.000s

Questions? Comments? Send me an email: [email protected]