55 lines
2.7 KiB
Plaintext
55 lines
2.7 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "e7323b89",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Ordered Fractions](https://projecteuler.net/problem=71)\n",
|
|
"\n",
|
|
"This problem can be solved by hand.\n",
|
|
"\n",
|
|
"The concept the problem is describing is called a [Farey sequence](https://en.wikipedia.org/wiki/Farey_sequence). The example given in the problem is $F_8$, and we are tasked with finding the numerator of the left neighbor of $\\frac{3}{7}$ in $F_{1000000}$.\n",
|
|
"\n",
|
|
"It turns out there is a very simple method for determining this. Whenever you have two neighbors $\\frac{a}{b}$ and $\\frac{c}{d}$ in a Farey sequence, the next term that will appear between them in a subsequent Farey sequence is simply $\\frac{a+c}{b+d}$, called the [mediant](https://w.wiki/EoNc) of the two neighbors. For example, since we're given that the left neighbor of $\\frac{3}{7}$ in $F_8$ is $\\frac{2}{5}$, the next fraction to appear between the two will be\n",
|
|
"$$\\frac{2+3}{5+7} = \\frac{5}{12}$$\n",
|
|
"Naturally, this fraction will first appear in $F_{12}$, meaning $\\frac{5}{12}$ is the left neighbor of $\\frac{3}{7}$ in that Farey sequence. We could then, in turn, find the mediant of $\\frac{5}{12}$ and $\\frac{3}{7}$ to find the next left neighbor of $\\frac{3}{7}$ ($\\frac{8}{19}$, appearing in $F_{19}$).\n",
|
|
"\n",
|
|
"We can repeat this process until we find a mediant with a denominator greater than 1000000. At that point, we know that mediant will *not* be in $F_{1000000}$, so whatever left neighbor we just used to calculate it must be the left neighbor of $\\frac{3}{7}$ in $F_{1000000}$.\n",
|
|
"\n",
|
|
"To compute this by hand, observe that the $n$th mediant computed in this manner is simply\n",
|
|
"$$\\frac{2 + 3n}{5 + 7n}$$\n",
|
|
"Therefore, we just need to find the largest $n$ such that $5 + 7n \\leq 1000000$, which is $n=142856$. This gives us a numerator of 428570.\n",
|
|
"\n",
|
|
"## Relevant sequences\n",
|
|
"* Numerators of Farey sequences: [A007305](https://oeis.org/A007305)\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
|
|
}
|