Question

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

\sqrt{2} = 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + ...}}} = 1.414213...

By expanding this for the first four iterations, we get:

\begin{aligned} 1 + \frac{1}{2} & = \frac{3}{2} = 1.5 \\ 1 + \dfrac{1}{2 + \dfrac{1}{2}} & = \frac{7}{5} = 1.4 \\ 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}} & = \frac{17}{12} = 1.41666... \\ 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}}} & = \frac{41}{29} = 1.41379... \end{aligned}

The next three expansions are \frac{99}{70}, \frac{239}{169}, and \frac{577}{408}, but the eighth expansion, \frac{1393}{985}, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Haskell

expansion :: [(Integer, Integer)]
expansion = iterate (\(n, d) -> (d, n + 2*d)) (1, 2)

main :: IO ()
main = print $ length [(n, d) | (n, d) <- take 1000 expansion, length (show (n + d)) > length (show d)]

$ ghc -O2 -o root-two root-two.hs
$ time ./root-two
real   0m0.011s
user   0m0.011s
sys    0m0.000s

Python

#!/usr/bin/env python
import fractions

def root_two(iterations):
    d = fractions.Fraction(1/2)
    for i in range(iterations):
        d = fractions.Fraction(1/(2+d))
        yield 1 + d

def main():
    print(len([f for f in root_two(1000) if len(str(f.numerator)) > len(str(f.denominator))]))

if __name__ == "__main__":
    main()

$ time python3 root-two.py
real   0m0.075s
user   0m0.067s
sys    0m0.008s