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)
Last Word
- More reading: e Continued Fraction from Mathworld
- Continued fraction for e from Todd and Vishal's blog
-
Run of the first 9 iterations at end of loop | 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 |