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