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

So, n₆ = 4*19 + 11 or 87 and n₁₀ = 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

Extended to solve all test cases for Project Euler Problem 65

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

Last Word