Ordered Fractions¶
This problem can be solved by hand.
The concept the problem is describing is called a 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}$.
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 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 $$\frac{2+3}{5+7} = \frac{5}{12}$$ 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}$).
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}$.
To compute this by hand, observe that the $n$th mediant computed in this manner is simply $$\frac{2 + 3n}{5 + 7n}$$ 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.
Relevant sequences¶
- Numerators of Farey sequences: A007305
Copyright (C) 2025 filifa¶
This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.