Project Euler Problem 65

Solution

Answer: 272

For the continued fraction of $e$,

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

the coefficients follow a simple pattern:

$$a_0=2,$$

and for $n\ge1$,

$$a_n= \begin{cases} 2k & \text{if } n=3k-1,\ 1 & \text{otherwise}. \end{cases}$$

We need the numerator of the $100^\text{th}$ convergent and then the sum of its digits.

---

Mathematical analysis

A continued fraction

$$[a_0;a_1,a_2,\dots,a_n]$$

has convergents $\frac{p_n}{q_n}$ generated recursively by:

$$p_n=a_n p_{n-1}+p_{n-2}$$

$$q_n=a_n q_{n-1}+q_{n-2}$$

with initial values

$$p_{-2}=0,\quad p_{-1}=1$$

$$q_{-2}=1,\quad q_{-1}=0.$$

These recurrences come directly from repeatedly evaluating the continued fraction from left to right.

---

For $e$, the terms are:

$$2,\ 1,\ 2,\ 1,\ 1,\ 4,\ 1,\ 1,\ 6,\ 1,\dots$$

The first few numerators are:

• $2$
• $3$
• $8$
• $11$
• $19$

matching the problem statement.

So the algorithm is:

1. Generate the first 100 coefficients.
2. Use the recurrence for convergents.
3. Take the numerator of the 100th convergent.
4. Sum its digits.

---

Python implementation

# Generate the first 100 coefficients for e's continued fraction

terms = [2]

k = 1
while len(terms) < 100:
    terms.extend([1, 2 * k, 1])
    k += 1

terms = terms[:100]

# Recurrence for convergents
# p = numerator, q = denominator

p_minus2, p_minus1 = 0, 1
q_minus2, q_minus1 = 1, 0

for a in terms:
    p = a * p_minus1 + p_minus2
    q = a * q_minus1 + q_minus2

    p_minus2, p_minus1 = p_minus1, p
    q_minus2, q_minus1 = q_minus1, q

# Numerator of the 100th convergent
numerator = p_minus1

# Sum of digits
digit_sum = sum(int(d) for d in str(numerator))

print(digit_sum)

---

Code walkthrough

Building the continued fraction terms

terms = [2]

The continued fraction starts with $2$.

terms.extend([1, 2 * k, 1])

This generates the repeating pattern

$$1,\ 2k,\ 1$$

giving:

$$1,2,1,1,4,1,1,6,1,\dots$$

until we have 100 terms.

---

Convergent recurrence

We store previous numerators and denominators:

p_minus2, p_minus1 = 0, 1
q_minus2, q_minus1 = 1, 0

Then for each coefficient $a$:

p = a * p_minus1 + p_minus2
q = a * q_minus1 + q_minus2

which implements:

$$p_n=a_n p_{n-1}+p_{n-2}$$

$$q_n=a_n q_{n-1}+q_{n-2}$$

---

Small-example verification

Using the first few terms:

$$[2] = \frac21$$

$$[2;1] = 3$$

$$[2;1,2] = \frac83$$

$$[2;1,2,1] = \frac{11}{4}$$

These exactly match the values given in the problem statement, confirming the recurrence is correct.

---

Final verification

The numerator of the 100th convergent is a very large integer, so a digit sum around a few hundred is reasonable. The computation uses exact integer arithmetic only, so there is no floating-point error.

Carrying out the calculation gives:

$$272$$

Answer: 272