Problem 65: Convergents of e

Mathematical Foundation

Theorem 1 (Euler, 1737). The continued fraction expansion of $e$ is

where the partial quotients are $a_0 = 2$ and for $k \ge 1$:

Proof. Euler derived this from the generalized continued fraction

using the relationship between $e$ and the confluent hypergeometric function. Specifically, consider the series $e = \sum_{n=0}^{\infty} 1/n!$ and apply Euler’s method of converting power series to continued fractions. The proof relies on the identity

from which the stated continued fraction for $e$ can be derived via equivalence transformations. A complete proof appears in Perron’s Die Lehre von den Kettenbruechen (1929). $\square$

Theorem 2 (Convergent Recurrence). The convergents $h_n/k_n = [a_0; a_1, \ldots, a_n]$ satisfy the recurrence

with initial conditions $h_{-1} = 1$, $h_0 = a_0$, $k_{-1} = 0$, $k_0 = 1$.

Proof. Define the matrix

We claim that

Base case ($n = 0$): $M_0 = \begin{pmatrix} a_0 & 1 \\ 1 & 0 \end{pmatrix}$, giving $h_0 = a_0$, $h_{-1} = 1$, $k_0 = 1$, $k_{-1} = 0$. Since $[a_0] = a_0/1$, this is correct.

Inductive step: Assume the product $M_0 \cdots M_{n-1}$ gives the correct matrix. Then

which gives $h_n = a_n h_{n-1} + h_{n-2}$ and $k_n = a_n k_{n-1} + k_{n-2}$. To see that $h_n/k_n = [a_0; a_1, \ldots, a_n]$, note that replacing $a_n$ by $a_n + 1/\alpha$ in the matrix product and using the inductive hypothesis on $[a_0; a_1, \ldots, a_{n-1}, a_n + 1/\alpha] = (h_{n-1}(a_n + 1/\alpha) + h_{n-2})/(k_{n-1}(a_n + 1/\alpha) + k_{n-2})$ confirms the identity. $\square$

Lemma 1 (Coprimality). For all $n \ge 0$, $\gcd(h_n, k_n) = 1$.

Proof. Taking determinants of the matrix product:

Since $h_n k_{n-1} - h_{n-1} k_n = \pm 1$, we have $\gcd(h_n, k_n) = 1$. $\square$

Lemma 2 (Growth Rate). The numerator $h_{99}$ has approximately $\sum_{k=0}^{99} \log_{10}(a_k)$ digits, which for the $e$ continued fraction yields about 57—58 digits.

Proof. From the recurrence $h_n = a_n h_{n-1} + h_{n-2} \ge a_n h_{n-1}$, so $\log_{10} h_n \ge \log_{10} a_n + \log_{10} h_{n-1}$. By induction, $\log_{10} h_n \ge \sum_{k=0}^n \log_{10} a_k$. The partial quotients for $e$ at indices $k \equiv 2 \pmod{3}$ are $2, 4, 6, \ldots, 66$ (for $k$ up to 98), contributing $\sum_{j=1}^{33} \log_{10}(2j) \approx 42$. The remaining 67 terms contribute $\log_{10}(1) = 0$ each (except $a_0 = 2$). Total: $\approx 42 + \log_{10}(2) \approx 42.3$. The actual numerator has 58 digits due to the additive term $h_{n-2}$ accumulating additional magnitude. $\square$

Editorial

We use Euler’s explicit pattern for the continued fraction of $e$ to determine the first $100$ partial quotients. The numerator of the convergents is then obtained from the standard recurrence, so only the two previous numerators need to be retained throughout the computation. Once the numerator of the $100$th convergent has been reached, we sum its decimal digits.

Pseudocode

Determine the partial quotients of $e$ from Euler's pattern:
    the first term is 2
    every third later term is an even number
    all remaining terms are 1

Initialize the recurrence with the two starting numerators.

Advance through the first 100 convergents:
    form the next numerator from the current partial quotient
    then shift the two stored numerators forward

After the last update, compute the decimal digit sum of the current numerator.
Return that sum.

Complexity Analysis

Time: The algorithm computes 100 iterations of the recurrence. Each iteration involves one big-integer multiplication and one big-integer addition. Since $h_{99}$ has $d \approx 58$ digits, each arithmetic operation costs $O(d)$ with schoolbook multiplication (or $O(d \log d)$ with FFT-based multiplication, though unnecessary here). Total: $O(100 \cdot d) = O(100 \cdot 58) = O(5800)$.

Space: $O(d) = O(58)$ for storing three big integers ($h_{n-2}$, $h_{n-1}$, $h_n$).

Answer

#include <bits/stdc++.h>
using namespace std;

// Simple big integer using vector of digits (least significant first)
struct BigInt {
    vector<int> d; // digits, d[0] is least significant

    BigInt(int x = 0) {
        if (x == 0) d.push_back(0);
        while (x > 0) { d.push_back(x % 10); x /= 10; }
    }

    BigInt operator+(const BigInt& o) const {
        BigInt res;
        res.d.clear();
        int carry = 0;
        for (int i = 0; i < (int)max(d.size(), o.d.size()) || carry; i++) {
            int s = carry;
            if (i < (int)d.size()) s += d[i];
            if (i < (int)o.d.size()) s += o.d[i];
            res.d.push_back(s % 10);
            carry = s / 10;
        }
        return res;
    }

    BigInt operator*(int x) const {
        BigInt res;
        res.d.clear();
        long long carry = 0;
        for (int i = 0; i < (int)d.size() || carry; i++) {
            long long s = carry;
            if (i < (int)d.size()) s += (long long)d[i] * x;
            res.d.push_back(s % 10);
            carry = s / 10;
        }
        while (res.d.size() > 1 && res.d.back() == 0) res.d.pop_back();
        return res;
    }

    int digit_sum() const {
        int s = 0;
        for (int x : d) s += x;
        return s;
    }
};

int main() {
    // Continued fraction of e: [2; 1, 2, 1, 1, 4, 1, 1, 6, ...]
    // a[0] = 2, a[k] for k>=1: if k%3==2 then 2*(k+1)/3 else 1
    auto a = [](int k) -> int {
        if (k == 0) return 2;
        if (k % 3 == 2) return 2 * (k + 1) / 3;
        return 1;
    };

    // Compute 100th convergent (index 99)
    BigInt h_prev2(1); // h_{-1} = 1
    BigInt h_prev1(a(0)); // h_0 = a_0 = 2

    for (int i = 1; i <= 99; i++) {
        BigInt h_new = h_prev1 * a(i) + h_prev2;
        h_prev2 = h_prev1;
        h_prev1 = h_new;
    }

    cout << h_prev1.digit_sum() << endl;
    return 0;
}

"""
Problem 65: Convergents of e

Find the sum of digits in the numerator of the 100th convergent
of the continued fraction for e.
"""

def solve():
    # Continued fraction of e: [2; 1, 2, 1, 1, 4, 1, 1, 6, ...]
    def a(k):
        if k == 0:
            return 2
        if k % 3 == 2:
            return 2 * (k + 1) // 3
        return 1

    # Convergent recurrence: h_n = a_n * h_{n-1} + h_{n-2}
    h_prev2 = 1   # h_{-1}
    h_prev1 = a(0)  # h_0

    for i in range(1, 100):
        h_new = a(i) * h_prev1 + h_prev2
        h_prev2 = h_prev1
        h_prev1 = h_new

    # h_prev1 is now h_99, the numerator of the 100th convergent
    return sum(int(d) for d in str(h_prev1))

answer = solve()
assert answer == 272
print(answer)