The square root of 2 can be written as an infinite continued fraction.
The infinite continued fraction can be written, , (2) indicates that 2 repeats ad infinitum. In a similar way, .
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 .
Hence the sequence of the first ten convergents for are:
What is most surprising is that the important mathematical constant, .
The first ten terms in the sequence of convergents for are:
The sum of digits in the numerator of the convergent is .
Find the sum of digits in the numerator of the convergent of the continued fraction for .
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
#!/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, 1) else: remainder = frac[1:len(frac)] (num, denom) = rationalize(remainder) return (frac * num + denom, num) numerator = rationalize(take(e(), 100)) print(sum(int(d) for d in str(numerator)))
$ time python3 continued.py real 0m0.020s user 0m0.016s sys 0m0.000s