What are Project Euler Problem # 57, Square Root Convergents?

Problem statement

The problem statement can be found here.

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 + \frac{1}{2 + ...}}}}$

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

$1 + \frac{1}{2} = \frac{3}{2} = 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...$

$1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}}} = \frac{41}{29} = 1.41379...$

Python code

Explanation

The problem is quite simple. All we have to do is generate the infinite fraction for the number of iterations specified (in this case, a $1000$) and return the number of continuous fractions where the number of digits of the numerator is greater than the number of digits in the denominator.

The first thing to notice is the pattern between the numerator and the denominator that will help us generate the next fractions.

If you look closely at the fractions you will notice the following pattern in the numerator and the denominators:

$\space\space \space \space \space \space \space \space \space \space \space \space \space n_{k+1} = n_{k} + 2*d$,

$\space\space \space \space \space \space \space \space \space \space \space \space \space d_{k+1} = n_{k+1} - d_k$,

where $n_i$ represents the numerator $i$ and $d$ is the denominator in a particular iteration.

Now we need a way to calculate the number of digits in the numbers. The brute force approach would take the $\left \lfloor{log_{10}}\right \rfloor$ of the number, and the result gives you the number of digits. However, taking the $log$ is a very computationally heavy operation.

A faster method to keep track of the number of digits is to have a counter variable initialized to $10$ and to increase the variable’s value by multiplying it by $10$ each time the number goes up a digit. So, for example, if our number is within $100$ and $999$ inclusive, our counter variable will store the value $1000$, indicating that the number is less than $1000$ and hence has $3$ digits.

In our code, we have two variables, num_dig and den_dig, that serve this purpose. Whenever the value of num_dig exceeds the value of den_dig, we know that the numerator has a greater number of digits than the denominator, and we can increase the count.