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:
$\sqrt(2) = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + ...}}}}$
The infinite continued fraction can be written as $\sqrt(2) = [1;(2)]; (2)$ indicates that 2 repeats ad infinitum. In a similar way, $\sqrt(23) = [4; (1,3,1,8)]$.
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 $\sqrt(2)$:
$1+\frac{1}{2}=3,\space\space1+\frac{1}{2 +\frac{1}{2}}=\frac{7}{5},\space\space1+\frac{1}{2 +\frac{1}{2 + \frac{1}{2}}}=\frac{17}{12}\space\space1+\frac{1}{2 +\frac{1}{2 + \frac{1}{2+ \frac{1}{2}}}}=\frac{41}{29}$.
Hence, the sequence of the first ten convergents for $\sqrt(2)$ is:
$1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}, \frac{1393}{985}, \frac{3363}{2378},...$
What is most surprising is that the important mathematical constant $e = [2; 1,2,1,1,4,1,1,6,1,...,1,2k,1,...].$
The first ten terms in the sequence of convergents for $e$ are:
$2,3,\frac{8}{3},\frac{11}{4}, \frac{19}{7}, \frac{87}{32},\frac{106}{39},\frac{193}{71},\frac{1264}{465},\frac{1457}{536},...$
The sum of digits in the numerator of the 10th convergent is $1 + 4 + 5+ 7 = 17$.
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for $e$.
The first thing to notice is that the value of the continuous fraction repeats with the pattern $1,2k,1$.
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:
$numerator_i = numerator_{i-1} * fraction_{i-1} + numerator_{i-2}$
def solution(N): n = 2 prev_n = 1 fract = 1 for k in range(2, N+1): temp = prev_n if (k % 3 == 0): fract = 2 * int(k/3) else: fract = 1 prev_n = n n = fract * prev_n + temp sum = digit_sum(n) print(sum) def digit_sum(num): sum = 0 while num > 0: sum = sum + (num % 10) num = num // 10 return sum solution(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 $1$ if k % 3
is not $0$ and $2k$ is k % 3
is $0$. This ensures that for each group of three consecutive values of $k$, one of them evaluates to $2k$.
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.
RELATED TAGS
CONTRIBUTOR
View all Courses