Project Euler Problem 65 Solution

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:

series to calculate the numerator forh convergent of the continued fraction

The multiplier, m, follows the infinite continued fraction [2; 1,2,1, 1,4,1, 1,6,1, … , 1,2k,1, …].

Continue fraction of e as an expression

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 logo

Solves all test cases for Hackerrank Project Euler Problem 65

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 program on repl.it Run Project Euler Problem 65 using Python on repl.it.

Last Word