Detailed mathematical approach

Problem Summary

The problem asks for the number of reduced fractions \(a/b\) that satisfy

$\frac{1}{3} \lt \frac{a}{b} \lt \frac{1}{2}, \qquad b \le 12000.$

So we are not listing all fractions with bounded denominator; we are counting only the reduced ones that fall inside one specific interval. The implementations do not scan every denominator and test coprimality. Instead, they treat \(\left(\frac13,\frac12\right)\) as a Stern-Brocot interval and count the admissible mediants generated inside it.

Mathematical Approach

The natural state is an interval whose endpoints are neighboring reduced fractions. For such an interval, the next fraction that can appear inside it is its mediant, and that observation leads directly to the recurrence used by the implementation.

Start from Farey neighbors

Let the current interval be

$\frac{a}{b} \lt \frac{c}{d}, \qquad bc-ad=1.$

The initial interval \(\frac13 \lt \frac12\) already has this property, because \(3\cdot 1 - 1\cdot 2 = 1\). Fractions with determinant \(1\) in this sense are neighbors in a Farey sequence and adjacent vertices in the Stern-Brocot tree.

The mediant of the two endpoints is

$\frac{a+c}{b+d}.$

It lies strictly between the endpoints because

$\frac{a}{b} \lt \frac{a+c}{b+d} \lt \frac{c}{d}.$

It is also automatically reduced. If some integer \(g\) divided both \(a+c\) and \(b+d\), then \(g\) would divide

$d(a+c)-c(b+d)=ad-bc=-1,$

so \(g=1\). This is why the algorithm never performs a \(\gcd\) check.

Why the mediant is the first fraction worth considering

The pruning rule in the code depends on a stronger fact: among all reduced fractions strictly between \(\frac{a}{b}\) and \(\frac{c}{d}\), the mediant has the smallest possible denominator.

Take any reduced fraction \(\frac{x}{y}\) with

$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}.$

Define

$m=cy-dx,\qquad n=bx-ay.$

Both numbers are positive because \(\frac{x}{y}\) lies strictly inside the interval. Using \(bc-ad=1\), we get

$ma+nc = a(cy-dx)+c(bx-ay)=x(bc-ad)=x,$

$mb+nd = b(cy-dx)+d(bx-ay)=y(bc-ad)=y.$

Hence

$x=ma+nc,\qquad y=mb+nd.$

Since \(m,n \ge 1\), it follows that

$y=mb+nd \ge b+d.$

Equality holds only when \(m=n=1\), which gives \(\frac{x}{y}=\frac{a+c}{b+d}\). Therefore the mediant is the unique interior reduced fraction with the smallest denominator. If \(b+d\gt N\), then no reduced fraction in that interval can have denominator at most \(N\), so the whole branch can be discarded immediately.

The determinant invariant survives every split

Once the mediant is inserted, the interval splits into

$\left(\frac{a}{b},\frac{a+c}{b+d}\right), \qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$

Both child intervals still satisfy the same determinant condition:

$b(a+c)-a(b+d)=bc-ad=1,$

$ (b+d)c-(a+c)d=bc-ad=1.$

So exactly the same reasoning applies recursively. Every admissible reduced fraction lies either to the left of the mediant or to the right of it, never both. That means the search space is partitioned without overlap, and every fraction in the target interval appears exactly once in this subtree.

The counting recurrence

Let

$T_N\!\left(\frac{a}{b},\frac{c}{d}\right)$

denote the number of reduced fractions \(\frac{x}{y}\) with \(y\le N\) and

$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d},$

under the invariant \(bc-ad=1\). Then the exact recurrence is

$ T_N\!\left(\frac{a}{b},\frac{c}{d}\right)= \begin{cases} 0, & b+d \gt N,\\[4pt] 1 + T_N\!\left(\frac{a}{b},\frac{a+c}{b+d}\right) + T_N\!\left(\frac{a+c}{b+d},\frac{c}{d}\right), & b+d \le N. \end{cases} $

The answer to the problem is therefore

$T_{12000}\!\left(\frac13,\frac12\right).$

This is not merely a heuristic tree walk. It is an exact decomposition of all reduced fractions in the interval, ordered by the Stern-Brocot structure.

Worked Example: \(N=8\)

Start with \(\frac13\) and \(\frac12\). Their mediant is \(\frac25\), and \(5 \le 8\), so \(\frac25\) contributes one count.

The left child interval is \(\left(\frac13,\frac25\right)\). Its mediant is \(\frac38\), and \(8 \le 8\), so that contributes another count. The next mediants below it have denominators \(11\) and \(13\), so that branch stops.

The right child interval is \(\left(\frac25,\frac12\right)\). Its mediant is \(\frac37\), and \(7 \le 8\), so it also counts. Its children would have denominators \(12\) and \(9\), both too large, so that branch stops as well.

The complete set is therefore

$\left\{\frac38,\frac25,\frac37\right\},$

so the count is \(3\). This is exactly the first checkpoint used by the implementations. Extending the same tree to \(N=12\) produces \(7\) fractions, matching the second checkpoint.

How the Code Works

The C++, Python, and Java implementations all start from the same state: the interval whose endpoints are \(\frac13\) and \(\frac12\). For each interval, the implementation computes the mediant numerator and denominator by simple addition. If the new denominator exceeds the limit, it returns \(0\) for that branch. Otherwise it counts that mediant and continues into the left and right child intervals.

The C++ and Java implementations express this logic directly as a recursive depth-first search. The Python implementation performs the same traversal with an explicit stack of intervals, which avoids recursion-depth issues while preserving the exact same recurrence and the exact same count.

Before solving the full case \(N=12000\), the code verifies the small benchmark cases \(N=8 \mapsto 3\) and \(N=12 \mapsto 7\). Those checkpoints confirm that the interval split, the stopping rule, and the one-count-per-mediant logic are all aligned with the mathematics above.

Complexity Analysis

Each valid fraction in the interval is generated exactly once, and each rejected branch ends after a constant amount of work. If \(A(N)\) denotes the number of reduced fractions in \(\left(\frac13,\frac12\right)\) with denominator at most \(N\), then the running time is \(O(A(N))\). For this problem, \(A(N)\) grows on the order of \(N^2\), so the algorithm is effectively quadratic in the bound, but with no wasted \(\gcd\) checks over irrelevant pairs.

The memory usage is \(O(H)\), where \(H\) is the depth of the search stack. In the recursive C++ and Java versions this is call-stack depth; in the Python version it is the size of the explicit stack. The worst-case depth is \(O(N)\) because some branches increase denominators only gradually, but the storage is still tiny compared with enumerating all candidate numerators and denominators directly.

Footnotes and References

1. Problem page: Project Euler 73
2. Farey sequence: Wikipedia - Farey sequence
3. Stern-Brocot tree: Wikipedia - Stern-Brocot tree
4. Mediant of fractions: Wikipedia - Mediant