Detailed mathematical approach

Problem Summary

We consider reduced proper fractions \(p/q\) with \(q \le 1{,}000{,}000\), list them in increasing order, and look for the fraction immediately to the left of \(3/7\). Equivalently, we want the largest reduced fraction strictly smaller than \(3/7\) whose denominator does not exceed \(10^6\). The winning fraction is \(428570/999997\), so the required numerator is \(428570\).

Mathematical Approach

The implementation does not construct the ordered list explicitly. Instead, it scans all denominators, computes the best possible numerator for each one, and maintains the largest reduced fraction found so far. That turns the ordering question into a clean arithmetic optimization problem.

The best numerator for a fixed denominator

Fix a denominator \(d\). To stay strictly left of \(3/7\), we need

$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$

Since \(3d\) is an integer, the largest integer \(n\) satisfying this strict inequality is obtained by replacing it with \(7n \le 3d - 1\). Therefore the only numerator worth testing for this denominator is

$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$

So every denominator contributes at most one serious candidate.

Why reduced fractions must be enforced

The ordered set in the problem contains each reduced proper fraction exactly once. If \(\gcd(n_d,d) \ne 1\), then \(n_d/d\) is only a non-reduced copy of a fraction that already appears with a smaller denominator. Such a candidate cannot be the new immediate left neighbor in the reduced list, so the implementations skip it.

Comparing candidates without floating point

Suppose the current best reduced fraction is \(a/b\), and the new candidate is \(n/d\). Because all denominators are positive, we can compare them exactly by cross-multiplication:

$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$

This avoids rounding issues and keeps the whole search in integer arithmetic.

The running invariant of the scan

After processing all denominators up to some value \(D\), the stored fraction is the largest reduced fraction below \(3/7\) among all denominators \(2,3,\dots,D\). The invariant is straightforward: when the next denominator arrives, its unique candidate is either discarded because it is not reduced, ignored because it is not better, or promoted because it is larger than the current best. By induction, the invariant remains true until the scan reaches \(10^6\).

Worked example: \(N = 8\)

The small checkpoint used by the implementations is \(N=8\). Evaluating the formula gives

$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6}\ \text{(not reduced)},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $

Among the reduced fractions strictly below \(3/7\), the largest is \(2/5\). That is why the checkpoint expects the numerator \(2\).

A theoretical cross-check from Farey neighbors

The scan is the method actually implemented, but the final answer can be verified number-theoretically. Adjacent reduced fractions \(a/b \lt c/d\) in a Farey sequence satisfy

$bc - ad = 1.$

For the predecessor \(p/q\) of \(3/7\), this becomes

$3q - 7p = 1.$

Hence \(3q \equiv 1 \pmod{7}\), so \(q \equiv 5 \pmod{7}\). The largest denominator with that residue and \(q \le 10^6\) is \(q=999997\). Substituting back gives

$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570.$

This confirms that the immediate left neighbor is exactly \(428570/999997\).

How the Code Works

The C++, Python, and Java implementations keep a current best numerator and denominator, initialized to \(0/1\). They iterate through every denominator from \(2\) up to the limit, compute \(n=\lfloor(3d-1)/7\rfloor\), reject the candidate when \(\gcd(n,d) \ne 1\), and otherwise compare \(n/d\) to the stored best fraction using cross-multiplication.

No fraction list is materialized, and no sorting is needed. Each loop iteration does one formula evaluation, one gcd test, and one exact comparison. The C++ and Python versions also include a small check at \(N=8\); the Java version runs the same scan directly for the full limit.

Complexity Analysis

The denominator scan performs \(N-1\) iterations. Each iteration uses constant-size integer arithmetic plus a gcd computation, so the total running time is \(O(N \log N)\) in the standard arithmetic model. For the fixed bound \(N=10^6\), this is easily fast enough.

The memory usage is \(O(1)\), because the implementation stores only the current best fraction and a handful of loop variables. A closed-form shortcut exists for this particular target, but the implemented scan is simple, exact, and general.

Footnotes and References

1. Problem page: Project Euler 71
2. Farey sequence: Wikipedia - Farey sequence
3. Mediant and neighboring fractions: Wikipedia - Mediant
4. Euclidean algorithm: Wikipedia - Euclidean algorithm
5. Modular arithmetic: Wikipedia - Modular arithmetic