Project Euler Problem 57 Solution

Question

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

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

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

1+12=32=1.51+12+12=75=1.41+12+12+12=1712=1.41666...1+12+12+12+12=4129=1.41379...\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 9970\frac{99}{70}, 239169\frac{239}{169}, and 577408\frac{577}{408}, but the eighth expansion, 1393985\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

Python