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?
Solution
We can see that our sequence \(\{a\}_k\) starts with \(a_0 = 1 + \frac{1}{2}\) and \(a_1 = 1 + \frac{1}{2 + \frac{1}{2}}\). We can now substitute \(a_0\) into \(a_1\), which gives \(a_1 = 1 + \frac{1}{1 + a_0}\). This is enough to state the recursive definition as:
\[a_{k+1} = 1 + \frac{1}{1 + a_k}\]
We could now use a fractional library and calculate the numerator and denomiator for each iteration and count the number of times the numerator has more digits than the denominator. But we could go further and evaluate the rational number by hand. That is
\[\begin{array}{rl} a_{k+1} &= 1 + \frac{1}{1 + a_k}\\ &= 1 + \frac{1}{1 + \frac{n_k}{d_k}}\\ &= 1 + \frac{1}{\frac{d_k + n_k}{d_k}}\\ &= 1 + \frac{d_k}{d_k + n_k}\\ &= \frac{d_k + n_k + d_k}{d_k + n_k}\\ &= \frac{2d_k + n_k}{d_k + n_k}\\ \end{array}\]
When we now calculate 1000 expansions on our recursive formula, we can check the length of each numerator and denominator using the number length function from Problem 25 and count accordingly:
import math
def solution(N=1000):
c = 0
n = d = 1
for k in range(N):
n, d = 2 * d + n, d + n
if int(math.log10(n)) > int(math.log10(d)):
c+= 1
return c Calling the log function 2000 times is really exhausting. We additionally save the current power of ten of the numerator and denominator and compare them instead of the logarithms:
def solution(N=1000):
c = 0
n = d = 1
np = dp = 10
for k in range(N):
n, d = 2 * d + n, d + n
if n >= np:
np*= 10
if d >= dp:
dp*= 10
if np > dp:
c+= 1
return c