Statement

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

$\sqrt{2} = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...$

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

$1 + 1/2 = 3/2 = 1.5$
$1 + 1/(2 + 1/2) = 7/5 = 1.4$
$1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...$
$1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...$

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 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?

Solution

In order to achieve the solution for this problem we will use one of Python's features: the yield instruction.

The yield instruction is used to implement generating functions. When a yield statement is executed, the state of the function is saved and the value is returned to the next's caller. On the following next call the function continues its execution from the last yield where its flow was stopped.

So I implemented a generator function that for each next that is sent to it, it returns the next fraction in the sequence.

from fractions import Fraction
from itertools import islice
 
def sqrt_2_continued_fraction():
    tmp = 2 + Fraction(1, 2)
    yield tmp
    while True:
        tmp = 2 + 1 / tmp
        result = 1 + 1 / tmp
        yield result
 
if __name__ == '__main__':
    result = sum(1 for frac in islice(sqrt_2_continued_fraction(), 1000) if
                 len(str(frac.numerator)) > len(str(frac.denominator)))
    print("The result is:", result)

The Python file is available for download here.