Trusted answers to developer questions

Muhammad Ashir

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...$

def solution(N): den = 1 num = 1 den_dig = 1 num_dig = 1 count = 0 for i in range(0, N): num = num + 2* den den = num - den if num >= num_dig: num_dig = num_dig * 10 if den >= den_dig: den_dig = den_dig * 10 if num_dig > den_dig: count += 1 print("Count:", count) N = 1000 solution(N)

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.

RELATED TAGS

project euler

CONTRIBUTOR

Muhammad Ashir

Copyright ©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses