## 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 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 (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,2`k`,1, …] which evaluates to (1,1,2,1,1,4,1,1,6,1,1,8,1,1, …).

So, n_{6} = 4*19 + 11 or **87** and n_{10} = 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,000^{th} 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.