 ## Project Euler & HackerRank Problem 65 Solution

##### Convergents of e
by {BetaProjects} | APRIL 10, 2009 | 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 (1, 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, …] which evaluates to (1,1,2,1,1,4,1,1,6,1,1,8,1,1, …).

So, n6 = 4*19 + 11 or 87 and n10 = 1*1264 + 193 or 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. 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 30000 from 100. This solution works for both.

### Python Source Code Use this link to download the Project Euler Problem 65: Convergents of e Python source. Run Project Euler Problem 65 using Python on repl.it