Square Root Convergents

Original description from the Project Euler:

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

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

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?

Solution:

By observation of the construction of this number sequence, we can identify that a new denominator comes from the sum of its prior numerator and denominator, while a new numerator comes from the sum of the prior denominator and the new denominator. For example, for the first fraction, we have \(\frac {3}{2}\). For the second fraction, we have \(\frac {2+(3+2)}{3+2}\).

Also because of this construction, by the Euclidean algorithm, we can show that all the pairs of numerators and denominators in this sequence are coprime, i.e. no common divisor greater than 1 exists between the numerator and the denominator. For example, regarding the third fraction \(\frac {17}{12}\),

Therefore, the greatest common divisor between 17 and 12 is 1. We can also identify the numerators and denominators of the first and the second fractions in this process of the Euclidean algorithm. It follows that all the numerators and denominators in fractions in the sequence have a greatest common divisor of 1 by mathematical induction. Namely, all the pairs of numerators and denominators in this sequence are coprime so we do not need to consider the reduction of the fractions. Therefore, we can use data types of double instead of a very long integer as it provides sufficient precision.

Source code in Python:

def solve_square_root_convergents():
    """This function is a wrapper function designed to solve the Square root convergents 
    problem (problem 57) in the ProjectEuler.
    
    return:
        count: the number of fractions containing a numerator with more digits than the 
        denominator in the first one-thousand expansions.
    """
    import math
    a = 2 #the first denominator
    b = 3 #the first numerator
    c = 0
    d = 0
    count = 0 #the number of fractions contain a numerator with more digits than the denominator
    for i in range(2,1001):
        c = a + b #the next denominator
        d = c + a #the next numerator
        a = c
        b = d
        if math.floor(math.log10(b)) - math.floor(math.log10(a)) == 1 :
            #if the numerator have more digits than the denominator
            count += 1
        if i == 800 : #reduce the number to avoid reaching the limits of double
            b= b/1e100
            a= a/1e100
    return count

print(solve_square_root_convergents()) #153

Reference:

Project Euler. Square root convergents. https://projecteuler.net/problem=57.