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...\displaystyle \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...\displaystyle \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

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.008s
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.100s
user   0m0.076s
sys    0m0.000s

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