It is possible to show that the square root of two can be expressed as an infinite continued fraction.
√ 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?
Assume previous expansion result is $ \frac{n}{d} $, then the next expansion is $ 1 + \frac{1}{1+\frac{n}{d}} = \frac{n+d+d}{n+d} $
import sys, os; sys.path.append(os.path.abspath('..'))
from timer import timethis
def generate_expansion():
n, d = 1, 1
while True:
yield n, d
n, d = 2 * d + n, n + d
@timethis
def solve():
cnt = 0
for i, e in enumerate(generate_expansion()):
if i >= 1000:
break
n, d = e
cnt += (len(str(n)) > len(str(d)))
return cnt
solve()