This problem statement can be found here.
The problem is as follows:
The square root of 2 can be written as an infinite continued fraction:
The infinite continued fraction can be written as indicates that 2 repeats ad infinitum. In a similar way, .
It turns out that the sequence of partial values of continued fractions for square roots provides the best rational approximations. Let us consider the convergents for :
.
Hence, the sequence of the first ten convergents for is:
What is most surprising is that the important mathematical constant
The first ten terms in the sequence of convergents for are:
The sum of digits in the numerator of the 10th convergent is .
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for .
The first thing to notice is that the value of the continuous fraction repeats with the pattern .
Since we are only interested in the numerator, we will try to find a pattern there. The following table will help us understand the relationship between the continuous fraction and the numerator value.
K | Continuous Fraction | Numerator |
1 | 1 | 2 |
2 | 2 | 3 |
3 | 1 | 8 |
4 | 1 | 11 |
5 | 4 | 19 |
6 | 1 | 87 |
7 | 1 | 106 |
8 | 6 | 193 |
9 | 1 | 1264 |
10 | 1 | 1457 |
The above table discloses the relationship between the numerator and the continuous fraction as:
def solution(N):n = 2prev_n = 1fract = 1for k in range(2, N+1):temp = prev_nif (k % 3 == 0):fract = 2 * int(k/3)else:fract = 1prev_n = nn = fract * prev_n + tempsum = digit_sum(n)print(sum)def digit_sum(num):sum = 0while num > 0:sum = sum + (num % 10)num = num // 10return sumsolution(100)
The code is pretty straightforward. We only need to keep track of the two most recent numerators. The variables n
and prev_n
are used to keep track of the last two numerators. The continuous fraction is if k % 3
is not and is k % 3
is . This ensures that for each group of three consecutive values of , one of them evaluates to .
Next, we update prev_n
to the current value of n
and store the value of prev_n
in the temp
variable to calculate the new value of n
, our next numerator.
Lastly, the sum_digit()
function takes in a number and returns the sum of its digits.
Free Resources