 ## Project Euler Problem 65 Solution

Convergents of e

by {BetaProjects} | Project Euler & HackerRank

### 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 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 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: The multiplier, m, follows the infinite continued fraction [2; 1,2,1, 1,4,1, 1,6,1, … , 1,2k,1, …]. So, n6 = 4*19 + 11 = 87 and n10 = 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,000th convergent is thousands of digits long, yet the digit sum is only 6 digits.

#### HackerRank version

HackerRank Project Euler 65 raises the limit to 30,000 from 100. This solution works for both.

### Python Source Code

``````nx, ny = 1, 2
L = int(input("Numerator of Nth convergent for e, N="))
for i in range(2, L+1):
m = 2*i//3 if i%3==0 else 1
nx, ny = ny, m*ny + nx

print (sum(map(int, str(ny))),ny)	`````` Run Project Euler Problem 65 using Python on repl.it.