[Python] Project Euler #65 - Convergents of e

Project Euler Problem #65 is related to continued fractions. Specifically, the problem is as follows:

The continued fraction expansion for the natural number e (Euler’s number) can be expressed in the following form:

\[ e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, \dots] \]

Here, the numbers inside the brackets represent the terms of the continued fraction expansion. The n-th convergent of the continued fraction uses these terms to produce a fraction. For example, the initial convergents for e are:
• 1st convergent: \(2\)
• 2nd convergent: \(\frac{3}{1}\)
• 3rd convergent: \(\frac{8}{3}\))

Continuing in this way, each convergent gets closer to the true value of \(e\).

---

Problem Requirement:

Calculate the 100th convergent of the continued fraction for e, and compute the sum of the digits in the numerator of that fraction.

"""
    Project Euler #65 - Convergents of e
        - by Aubrey Choi
        - created at 2015-02-19
"""
ub = 100
res = 0

d = 1
n = 2

for i in range(2, ub+1):
    t = d
    c = 1
    if i%3 == 0: c = 2*int(i/3)
    d = n
    n = c * d + t

for c in str(n):
    res = res + int(c)

print(res)

 

1. Calculating the Numerator of the 100th Convergent
The first for loop iteratively calculates the numerator of each convergent of e, from the 2nd up to the 100th. It uses the following recurrence relation for the numerators:

 

\[ N_i = a_i \cdot N_{i-1} + N_{i-2} \]

where:
\(N_i\) is the numerator of the i-th convergent.
\(N_{i−1}\)) and \(N_{i−2}\) are the numerators of the two previous convergents.
\(a_i\) is the i-th term in the continued fraction sequence for e, which is [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ...].

In the code:
The loop runs from i = 2 to 100 (ub).
At the beginning of each iteration i:
n holds the value of the previous numerator, \(N_{i−1}\).
d holds the value of the numerator before that, \(N_{i−2}\).
c is calculated to be the term \(a_i\). The code correctly identifies the pattern that for the continued fraction of e, \(a_i\)  is 2 * (i/3) when i is a multiple of 3, and 1 otherwise. (Note: The sequence of \(a_i\) in this code corresponds to the terms after the initial 2;).
The line n = c * d + t (where t is a temporary store for the old d) calculates the new numerator, \(N_i\).  By the end of the loop, n holds the numerator of the 100th convergent.

2. Summing the Digits of the Numerator
The second for loop performs a simple task:
It converts the final numerator n (which is a very large number) into a string.
It then iterates through each character of the string.
For each character, it converts it back to an integer and adds it to the res variable.
Finally, it prints the total sum stored in res.