This problem statement can be found [here](https://projecteuler.net/problem=65).

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

# Solution

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.



align-center

The above table discloses the relationship between the numerator and the continuous fraction as:
# Code
$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. 

Convergents of e (Project Euler #65)

Analyzing patterns in continued fractions, the relationship between the numerator and fractions is deduced, focusing on the 100th convergent of e.

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