Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

project euler

Convergents of e (Project Euler #65)

Muhammad Ashir

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:

(2)=1+12+12+12+12+...\sqrt(2) = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + ...}}}}

The infinite continued fraction can be written as (2)=[1;(2)];(2)\sqrt(2) = [1;(2)]; (2) indicates that 2 repeats ad infinitum. In a similar way, (23)=[4;(1,3,1,8)]\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 (2)\sqrt(2):

1+12=3,  1+12+12=75,  1+12+12+12=1712  1+12+12+12+12=41291+\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 (2)\sqrt(2) is:

1,32,75,1712,4129,9970,239169,577408,1393985,33632378,...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,...].e = [2; 1,2,1,1,4,1,1,6,1,...,1,2k,1,...].

The first ten terms in the sequence of convergents for ee are:

2,3,83,114,197,8732,10639,19371,1264465,1457536,...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=171 + 4 + 5+ 7 = 17.

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for ee.

Solution

The first thing to notice is that the value of the continuous fraction repeats with the pattern 1,2k,11,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

numeratori=numeratori1fractioni1+numeratori2numerator_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 11 if k % 3 is not 00 and 2k2k is k % 3 is 00. This ensures that for each group of three consecutive values of kk, one of them evaluates to 2k2k.

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

Muhammad Ashir
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring