149 lines
3.4 KiB
Plaintext
149 lines
3.4 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "bdec47c4",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Convergents of $e$](https://projecteuler.net/problem=65)\n",
|
|
"\n",
|
|
"Easy one-liner in SageMath."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "8a93028c",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"272"
|
|
]
|
|
},
|
|
"execution_count": 1,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"sum(continued_fraction(e).convergent(99).numerator().digits())"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "396468b7",
|
|
"metadata": {},
|
|
"source": [
|
|
"To compute the convergents ourselves, we'll first make a generator for the partial denominators of the continued fraction of $e$."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "bedc34c8",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from itertools import count, chain\n",
|
|
"\n",
|
|
"def partial_denominators_e():\n",
|
|
" yield 2\n",
|
|
" yield from chain.from_iterable((1, 2 * k, 1) for k in count(1))"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "33288cd0",
|
|
"metadata": {},
|
|
"source": [
|
|
"Then we'll apply a simple algorithm for computing [convergents using the partial denominators](https://en.wikipedia.org/wiki/Simple_continued_fraction) (outside of SageMath, you might want to use a [fraction type](https://docs.python.org/3/library/fractions.html))."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "1f7bab23",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def convergents(partial_denoms):\n",
|
|
" h, hprev = 1, 0\n",
|
|
" k, kprev = 0, 1\n",
|
|
" for b in partial_denoms:\n",
|
|
" h, hprev = b * h + hprev, h\n",
|
|
" k, kprev = b * k + kprev, k\n",
|
|
" yield h/k"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "99b790f3",
|
|
"metadata": {},
|
|
"source": [
|
|
"Now just iterate until we reach the 100th convergent."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 4,
|
|
"id": "5b8189b7",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"272"
|
|
]
|
|
},
|
|
"execution_count": 4,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"for (i, c) in enumerate(convergents(partial_denominators_e())):\n",
|
|
" if i == 99:\n",
|
|
" break\n",
|
|
"\n",
|
|
"sum(c.numerator().digits())"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "5778175d",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Relevant sequences\n",
|
|
"* Numerators of convergents of $e$: [A007676](https://oeis.org/A007676)\n",
|
|
"\n",
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"language": "sage",
|
|
"name": "sagemath"
|
|
},
|
|
"language_info": {
|
|
"codemirror_mode": {
|
|
"name": "ipython",
|
|
"version": 3
|
|
},
|
|
"file_extension": ".py",
|
|
"mimetype": "text/x-python",
|
|
"name": "python",
|
|
"nbconvert_exporter": "python",
|
|
"pygments_lexer": "ipython3",
|
|
"version": "3.11.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|