Project Euler 65: Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e

Project Euler 65: Problem Description

Project Euler 65: The square root of 2 can be written as an infinite continued fraction.

The infinite continued fraction can be written, √2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, √23 = [4;(1,3,1,8)].

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for √2.

Hence the sequence of the first ten convergents for √2 are:

What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

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.

Analysis

The numerator follows a predictable pattern (sequence) and we are exploiting that to solve this problem. There is a multiplier, m, that follows the sequence mentioned in the problem statement [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …] starting with the third term, m₂. The numerator follows the sequence (1, 2, 3, 8, 11, 19, 87, …) as defined below:

So, n₆ = 4*19 + 11 or 87 and n₁₀ = 1*193 + 1264 or 1457

HackerRank asks for the sum of digits in the numerator for up to the 30,000th convergent and is solved with no problem.

This program and method
solves all test cases for
Project Euler 65 on HackerRank

Project Euler 65 Solution

Afterthoughts

• Imagine, if you will, that n0 and n1 are crappy variable names and become n2, n3, then n4, n5 and so one with each iteration.
  
• See also, Project Euler 57 Solution:
  

Project Euler 65