Project Euler Problem 65 Solution: Convergents of <i>e</i>

Project Euler Problem 65 Statement

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

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …

The sum of digits in the numerator of the 10^th convergent is 1+4+5+7=17.

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

Solution

The numerator, n, for the continued fraction follows a predictable pattern (2, 3, 8, 11, 19, 87, …) and we are exploiting that to solve this problem:

$$n_i = m_i * n_{i-1} + n_{i-2}, \text{where}\:n_0=1\:\text{and}\:n_1=2$$

The multiplier, m, follows the infinite continued fraction [2; 1,2,1, 1,4,1, 1,6,1, … , 1,2k,1, …].

$$e = 2 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 1/(4 + \ldots)))))$$

So, n₆ = 4*19 + 11 = 87 and n₁₀ = 1*1264 + 193 = 1457

Instead of the numerator, which grows to hundreds of digits rapidly, we are asked for the numerator’s digit sum because it’s a much smaller number to enter as an answer for Project Euler. It has absolutely nothing to do with solving the problem. For example, the numerator for the 30,000^th convergent is thousands of digits long, yet the digit sum is only 6 digits.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 65

HackerRank Project Euler 65 raises the limit to 30,000.

Python Source Code

import sys
sys.set_int_max_str_digits(0)  # Remove the 4300 digit limit

nx, ny = 1, 2
for i in range(2, int(input())+1):
    m = 2*i//3 if i%3==0 else 1
    nx, ny = ny, nx + ny*m

print (sum(map(int, str(ny))))

Last Word

Sadly, we need to change the behavior of Python 3.9 to allow us to do what we always did before with impunity.
```
import sys
sys.set_int_max_str_digits(0)  # Remove the 4300 digit limit
```
The loop starts processing the expansion from the second term onwards, because the first term is aleady defined as the initial values of nx and ny.
More reading: e Continued Fraction from Mathworld
Continued fraction for e from Todd and Vishal's blog

         The first 9 iterations 
      at the end of loop for N=10
	| i  |  nx  |  ny  | m |
	| 2  | 2    | 3    | 1 |
	| 3  | 3    | 8    | 2 |
	| 4  | 8    | 11   | 1 |
	| 5  | 11   | 19   | 1 |
	| 6  | 19   | 87   | 4 |
	| 7  | 87   | 106  | 1 |
	| 8  | 106  | 93   | 1 |
	| 9  | 193  | 1264 | 6 |
	| 10 | 1264 | 1457 | 1 |
	answer: 1+4+5+7 = 17