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{aliged} &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{aligned}$$
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.