Related Tags

project euler

# Convergents of e (Project Euler #65)

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

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

 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:

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

RELATED TAGS

project euler

CONTRIBUTOR