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

$\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?

expansion :: [(Integer, Integer)]
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
sys    0m0.008s