Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

project euler

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

Muhammad Ashir

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:

(2)=1+12+12+12+12+...\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+12=32=1.51 + \frac{1}{2} = \frac{3}{2} = 1.5

1+12+12=75=1.41 + \frac{1}{2 + \frac{1}{2}} = \frac{7}{5} = 1.4

1+12+12+12=1712=1.41666...1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} = \frac{17}{12} = 1.41666...

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

Python code


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)

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 10001000) 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:

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

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

where nin_i represents the numerator ii and dd 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 log10\left \lfloor{log_{10}}\right \rfloor of the number, and the result gives you the number of digits. However, taking the loglog 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 1010 and to increase the variable’s value by multiplying it by 1010 each time the number goes up a digit. So, for example, if our number is within 100100 and 999999 inclusive, our counter variable will store the value 10001000, indicating that the number is less than 10001000 and hence has 33 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