It is possible to show that the square root of two can be expressed as an infinite continued fraction.
\(\sqrt 2 =1+ \frac 1 {2+ \frac 1 {2 +\frac 1 {2+ \dots}}}\)
By expanding this for the first four iterations, we get:
\(1 + \frac 1 2 = \frac 32 = 1.5\)
\(1 + \frac 1 {2 + \frac 1 2} = \frac 7 5 = 1.4\)
\(1 + \frac 1 {2 + \frac 1 {2+\frac 1 2}} = \frac {17}{12} = 1.41666 \dots\)
\(1 + \frac 1 {2 + \frac 1 {2+\frac 1 {2+\frac 1 2}}} = \frac {41}{29} = 1.41379 \dots\)
The next three expansions are \(\frac {99}{70}\), \(\frac {239}{169}\), and \(\frac {577}{408}\), but the eighth expansion, \(\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 the denominator?
Let the \(n\)-th convergent be \(\frac{a_n}{b_n}\), when \(\frac{a_1}{b_1} = \frac 32\). Then
\[ \frac{a_n}{b_n} = 1 + \frac{1}{1 + \frac{a_{n-1}}{b_{n-1}}} = 1 + \frac{b_{n-1}}{a_{n-1} + b_{n-1}} = \frac{a_{n-1} + 2b_{n-1}}{a_{n-1} + b_{n-1}}. \]Assume inductively that \(\frac{a_{n-1}}{b_{n-1}}\) is in lowest terms; that is, \(\gcd(a_{n-1},b_{n-1}) = 1\). Then
\begin{align} \gcd(a_n, b_n) &= \gcd(a_{n-1} + 2b_{n-1}, a_{n-1} + b_{n-1}) \\ &= \gcd(b_{n-1}, a_{n-1} + b_{n-1}) \\ &= \gcd(b_{n-1}, a_{n-1}) \\ &= 1, \end{align}and so \(\frac{a_n}{b_n}\) is also in lowest terms. Therefore \(a_n = a_{n-1} + 2b_{n-1}\) and \(b_n = a_{n-1} + b_{n-1}\) for all \(n\).
def p57(C = 1000):
a, b = 3, 2
res = 0
for n in range(2, C+1):
a, b = a + 2*b, a + b
if len(str(a)) > len(str(b)):
res += 1
return res