Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.
Solution
This problem can be solved with pen and paper quite rapidly. Since we want a fraction with a denominator less than one million, we can scale \(\frac{3}{7}\) to \(\frac{428571}{999999}\) and simply subtract one from the nominator to make it less than \(\frac{3}{7}\) or more formally:
\[\frac{3}{7}=\frac{428571}{999999}>\frac{428571-1}{999999}\]
This only works so easy since \(9999999\) can be divideed by \(7\) perfectly. If we look for a general solution, the problem statement reads like the definition of a Farey sequence. A Farey sequence \(F_N\) of order \(N\) is an ordered set of reduced fractions \(\frac{p_i}{q_i}\) with \(p_i\leq q_i\leq N, i\in I, gcd(p_i, q_i)=1\), such that \(\frac{p_i}{q_i}<\frac{p_j}{q_j}\;\forall i<j\).
The first instances of the set are:
\[\begin{array}{rl} F_{1}&=\left({\tfrac {0}{1}},{\tfrac {1}{1}}\right)\\ F_{2}&=\left({\tfrac {0}{1}},{\tfrac {1}{2}},{\tfrac {1}{1}}\right)\\ F_{3}&=\left({\tfrac {0}{1}},{\tfrac {1}{3}},{\tfrac {1}{2}},{\tfrac {2}{3}},{\tfrac {1}{1}}\right)\\ F_{4}&=\left({\tfrac {0}{1}},{\tfrac {1}{4}},{\tfrac {1}{3}},{\tfrac {1}{2}},{\tfrac {2}{3}},{\tfrac {3}{4}},{\tfrac {1}{1}}\right)\\ F_{5}&=\left({\tfrac {0}{1}},{\tfrac {1}{5}},{\tfrac {1}{4}},{\tfrac {1}{3}},{\tfrac {2}{5}},{\tfrac {1}{2}},{\tfrac {3}{5}},{\tfrac {2}{3}},{\tfrac {3}{4}},{\tfrac {4}{5}},{\tfrac {1}{1}}\right) \end{array}\]
So, Farey sequences are an easy way to generate an ordered set, but we don't need the full set. We only need a path towards the closest fraction to the goal \(\frac{3}{7}\) within the set and this can be done in a divide and conquer fashion by working on an interval which gets refined iteratively, starting on the interval \(\left[\frac{0}{1}, \frac{1}{1}\right]\) and interpolating each interval with the mediant \(m\) where the numerators and denominators of the interval boundaries are getting added:
\[\begin{array}{rl} \left[\frac{0}{1}, \frac{1}{1}\right] &\rightarrow m = \frac{0+1}{1+1}=\frac{1}{2} \text{ larger than }\frac{3}{7}\\ \left[\frac{0}{1}, \frac{1}{2}\right] &\rightarrow m = \frac{0+1}{1+2}=\frac{1}{3} \text{ smaller than }\frac{3}{7}\\ \left[\frac{1}{3}, \frac{1}{2}\right] &\rightarrow m = \frac{1+1}{3+2}=\frac{2}{5} \text{ smaller than }\frac{3}{7}\\ \left[\frac{2}{5}, \frac{1}{2}\right] &\rightarrow m = \frac{2+1}{5+2}=\frac{3}{7} \text{ equal to }\frac{3}{7}\\ \left[\frac{2}{5}, \frac{3}{7}\right] &\rightarrow m = \frac{2+3}{5+7}=\frac{5}{12} \text{ larger than }\frac{3}{7}\\ \end{array} \]
When the mediant is larger or equal to the goal fraction, we adjust the lower end of the interval and if the mediant is smaller to the goal fraction, we adjust the upper end of the interval. Interpolating a fraction using the mediant was proven to result in a irreducible fraction. Looking at the mediants starting with \(\frac{2}{5}\), an interesting pattern is emerging:
\[\begin{array}{rl} \frac{5}{12} &= \frac{2 + 3}{5 + 7}\\ \frac{8}{19} &= \frac{2 + 3 \cdot 2}{5 + 7\cdot 2}\\ \frac{11}{26} &= \frac{2 + 3 \cdot 3}{5 + 7\cdot 3}\\ \ldots&= \ldots\\ &= \frac{2 + 3k}{5 + 7k} \end{array}\]
Now the denominator is limited by 1M:
\[\begin{array}{rrl} & 5 + 7k &\leq 1000000\\ \Leftrightarrow & 7k &\leq 999995\\ \Leftrightarrow & k &\leq \frac{999995}{7}\\ \Rightarrow & k &= \left\lfloor\frac{999995}{7}\right\rfloor\\ \Leftrightarrow & k &= 142856 \end{array}\]
Therefore we have a closed form to calculate the nominator using \(2+3k\).