Detailed mathematical approach

Problem Summary

The regular continued fraction of Euler's number is

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

The task is to take the 100th convergent of this continued fraction, extract its numerator, and compute the sum of that numerator's decimal digits. The first convergent is \(2/1\), so the requested object is the rational number obtained after processing coefficients \(a_0\) through \(a_{99}\).

This is an exact arithmetic problem, not a floating-point approximation problem. Once the coefficient pattern of the continued fraction is known, the numerator and denominator of each convergent follow from a short integer recurrence.

Mathematical Approach

Write the convergents as

$K_n = [a_0; a_1, a_2, \dots, a_n] = \frac{p_n}{q_n}.$

For this problem we need the digit sum of \(p_{99}\), because \(K_{99}\) is the 100th convergent.

The coefficient pattern for \(e\)

The continued fraction coefficients are not arbitrary. They follow the explicit pattern

$a_0 = 2,$

and for every integer \(m \ge 1\),

$a_{3m-2} = 1, \qquad a_{3m-1} = 2m, \qquad a_{3m} = 1.$

Equivalently, for \(k \ge 1\),

$a_k = \begin{cases} \dfrac{2(k+1)}{3}, & k \equiv 2 \pmod{3}, \\ 1, & \text{otherwise}. \end{cases}$

So the sequence after the initial 2 is grouped into triples \(1, 2, 1\), \(1, 4, 1\), \(1, 6, 1\), and so on. This pattern is the only problem-specific input the algorithm needs.

Recurrence for convergents

Every regular continued fraction has the standard recurrence

$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}.$

The implementations use the initialization

$p_{-1} = 1, \qquad p_0 = 2, \qquad q_{-1} = 0, \qquad q_0 = 1.$

That means the first convergent \(2/1\) is already loaded before the loop starts. Each later coefficient appends one more layer to the continued fraction, and one recurrence step advances from \(K_{n-1}\) and \(K_{n-2}\) to \(K_n\).

An invariant that explains why no reduction is needed

The recurrence preserves the determinant identity

$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}.$

Since the right-hand side is always \(\pm 1\), every pair \((p_n, q_n)\) is coprime. So the convergents are automatically in lowest terms, and there is never any need to compute a greatest common divisor or reduce a fraction explicitly.

This also explains why the denominator is still tracked in the code even though the final answer only uses the numerator: the numerator and denominator evolve together under the same recurrence and describe the convergent exactly at every step.

Worked example: the 10th convergent

The first ten coefficients are

$2; 1, 2, 1, 1, 4, 1, 1, 6, 1.$

Applying the recurrence produces

$\frac{2}{1}, \ \frac{3}{1}, \ \frac{8}{3}, \ \frac{11}{4}, \ \frac{19}{7}, \ \frac{87}{32}, \ \frac{106}{39}, \ \frac{193}{71}, \ \frac{1264}{465}, \ \frac{1457}{536}.$

For instance,

$p_1 = 1 \cdot 2 + 1 = 3, \qquad p_2 = 2 \cdot 3 + 2 = 8, \qquad p_5 = 4 \cdot 19 + 11 = 87.$

So the 10th convergent has numerator \(1457\), and its digit sum is

$1 + 4 + 5 + 7 = 17.$

This is the natural checkpoint for the implementation: if term 10 does not give 17, then the indexing or the coefficient pattern is wrong.

From the recurrence to the requested answer

After processing coefficients \(a_1\) through \(a_{99}\), the numerator is exactly the numerator of the 100th convergent. The final step is purely decimal: convert that integer to base 10 and add its digits. No symbolic simplification, no search, and no approximation theory beyond the convergent recurrence is required.

How the Code Works

The C++, Python, and Java implementations all follow the same structure.

Generate the continued-fraction coefficients

The first coefficient is fixed at \(2\). For every later index, the implementation checks whether the index is congruent to \(2\) modulo \(3\). If not, the coefficient is \(1\); if so, the coefficient is the corresponding even number \(2, 4, 6, \dots\).

Advance a rolling two-term state

The implementation stores the current and previous numerators, and the current and previous denominators. Each loop iteration reads the next coefficient \(a_n\), computes

$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2},$

and then shifts the state forward. Because the first convergent \(2/1\) is already the initial state, term 1 returns immediately and term \(t\) needs exactly \(t-1\) updates.

Sum the digits of the final numerator

Once the requested convergent has been built, the implementation converts its numerator to a decimal string and adds the characters' digit values. A built-in checkpoint verifies that the 10th convergent produces digit sum \(17\) before the default 100th-term calculation is trusted.

Complexity Analysis

If \(t\) is the requested term and \(D\) is the number of decimal digits in the final numerator, then the algorithm performs \(t-1\) big-integer updates. Writing \(M(D)\) for the cost of multiplying a \(D\)-digit integer by a small coefficient and adding another \(D\)-digit integer, the running time is \(O(t \cdot M(D))\). With schoolbook arithmetic this behaves like \(O(tD)\).

For the specific input \(t = 100\), the computation is tiny. The implementation stores only the current and previous numerator/denominator pairs, plus the decimal representation used during the final digit sum, so the space usage is \(O(D)\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=65
2. Continued fractions: Wikipedia - Continued fraction
3. Convergents: Wikipedia - Convergents of continued fractions
4. Euler's number: Wikipedia - e
5. Coefficient sequence of the continued fraction for \(e\): OEIS A003417