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