Project Euler Problem 57 Solution
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
By expanding this for the first four iterations, we get:
The next three expansions are , , and , but the eighth expansion, , 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)] 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
#!/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@example.com