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