Project Euler Solution 65: Convergents of e

Project Euler Problem Problem 65: Convergents of e continues with the continued fractions, but this time about Euler's constant.

The square root of 2 can be written as an infinite continued fraction. $$\sqrt{2} = 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + ...}}}}$$

The infinite continued fraction can be written, $\sqrt{2} = [1; (2)]$ indicates that 2 repeats ad infinitum. In a similar way, $\sqrt{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 $\sqrt 2$. $$\begin{align} &1 + \dfrac{1}{2} = \dfrac{3}{2} \ &1 + \dfrac{1}{2 + \dfrac{1}{2}} = \dfrac{7}{5}\ &1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}} = \dfrac{17}{12}\ &1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}}} = \dfrac{41}{29} \end{align}$$

Hence the sequence of the first ten convergents for $\sqrt 2$: $$ 1, \dfrac{3}{2}, \dfrac{7}{5}, \dfrac{17}{12}, \dfrac{41}{29}, \dfrac{99}{70}, \dfrac{239}{169}, \dfrac{577}{408}, \dfrac{1393}{985}, \dfrac{3363}{2378}, ... $$

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 sum of digits in the numerator of the 10th convergent is $1 + 4 + 5 + 7 = 17$.

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

This isn't as difficult as the previous one. We just have to simplify a partial continued fraction until it is a simple fraction. For that we can write a test that uses the examples:

def test_convergent_from_sequence() -> None:
    assert convergent_from_sequence([1, 2]) == (3, 2)
    assert convergent_from_sequence([1, 2, 2]) == (7, 5)
    assert convergent_from_sequence([1, 2, 2, 2]) == (17, 12)
    assert convergent_from_sequence([1, 2, 2, 2, 2]) == (41, 29)

Then we write the function to fulfil the test. This is just simplifying the fractions, cancelling and inverting. For the cancellation we use greatest_common_denominator from Solution 33: Digit cancelling fractions.

def convergent_from_sequence(coefficients: list[int]) -> tuple[int, int]:
    denominoator = 1
    numerator = coefficients[-1]
    for coefficient in reversed(coefficients[:-1]):
        numerator, denominoator = denominoator, numerator
        numerator += coefficient * denominoator
    gcd = greatest_common_denominator(numerator, denominoator)
    numerator //= gcd
    denominoator //= gcd
    return numerator, denominoator

We need to write a generator for the coefficients of $e$. This is best done with a test first:

def test_continued_fraction_e() -> None:
    expected = [2, 1, 2, 1, 1, 4, 1, 1, 6, 1]
    actual = list(itertools.islice(continued_fraction_e(), len(expected)))
    assert actual == expected

Implementing it as a generator is easy, we don't have to think about indices and can just generate these triplets:

def continued_fraction_e() -> Iterator[int]:
    yield 2
    for k in itertools.count(1):
        yield 1
        yield 2 * k
        yield 1

From here we can combine these things and specify a generator for the convergents:

def test_convergents_series_e() -> None:
    expected = [
        (2, 1),
        (3, 1),
        (8, 3),
        (11, 4),
        (19, 7),
        (87, 32),
        (106, 39),
        (193, 71),
        (1264, 465),
        (1457, 536),
    ]
    actual = list(
        itertools.islice(convergents_series(continued_fraction_e()), len(expected))
    )
    assert actual == expected

This is implemented straightforwardly using the functions that we already have:

def convergents_series(coefficients: Iterator[int]) -> Iterator[int]:
    coefficients_so_far = []
    for coefficient in coefficients:
        coefficients_so_far.append(coefficient)
        yield convergent_from_sequence(coefficients_so_far)

Writing the solution then becomes easy. We just take the 100th element of the sequence, take the numerator and use the digit sum from Solution 56: Powerful digit sum.

def solution() -> int:
    fractions = list(
        itertools.islice(convergents_series(continued_fraction_e()), 99, 100)
    )
    return digit_sum(fractions[0][0])

That computes the solution in 972 µs, and I think that this is fast enough. I don't think that one could somehow reuse the partial fractions.