Detailed mathematical approach

Problem Summary

For a denominator bound \(B\), a rational \(r/s\) with \(s \le B\) is called a best approximation to a real number \(x\) if it minimizes \(|x-r/s|\) among all rationals whose denominators do not exceed \(B\). A rational number \(x\) is called ambiguous if there exists at least one bound \(B\) for which two distinct rationals are tied as best approximations.

The problem asks for the number of reduced rationals \(x=p/q\) such that \(0 \lt x \lt 1/100\), \(q \le 10^8\), and \(x\) is ambiguous. The successful strategy is not to enumerate all fractions with denominator up to \(10^8\), but to characterize exactly which rationals can be ambiguous and count only those.

Mathematical Approach

The central objects are neighboring Farey fractions. Every ambiguous rational in the target range comes from one Farey gap, and the denominator condition on \(x\) becomes a simple product condition on the two endpoint denominators.

Ambiguity means a midpoint of Farey neighbors

Assume a denominator bound \(B\) gives two distinct best approximations \(a/b\) and \(c/d\) with \(a/b \lt x \lt c/d\) and \(b,d \le B\). There cannot be any reduced fraction \(u/v\) with \(v \le B\) strictly between them, because such a fraction would be closer to \(x\) than at least one endpoint. Therefore \(a/b\) and \(c/d\) must be adjacent in the Farey sequence of order \(B\), which is equivalent to

$bc-ad=1.$

Since the two errors are equal, \(x\) must be exactly the midpoint of the interval:

$x=\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right)=\frac{ad+bc}{2bd}.$

The converse is equally important. If \(a/b \lt c/d\) are Farey neighbors and \(B\) satisfies \(\max(b,d)\le B \lt b+d\), then no reduced fraction with denominator at most \(B\) lies between them. At the midpoint, both endpoints are therefore equally close and both are best approximations. So ambiguous rationals are exactly the midpoints of neighboring Farey fractions.

The denominator of the midpoint is exactly \(2bd\)

The midpoint formula does not simplify unexpectedly. From \(bc-ad=1\), the products \(bc\) and \(ad\) have opposite parity, so \(ad+bc\) is odd. Also,

$\gcd(ad+bc,b)=\gcd(ad,b)=1,\qquad \gcd(ad+bc,d)=\gcd(bc,d)=1.$

Hence \(\gcd(ad+bc,2bd)=1\), and the midpoint is already in lowest terms with denominator

$q=2bd.$

This is why the denominator limit \(q \le Q\) becomes

$2bd \le Q \qquad\Longleftrightarrow\qquad bd \le \left\lfloor\frac{Q}{2}\right\rfloor,$

with \(Q=10^8\). In other words, the whole denominator constraint is encoded by the product of the two Farey-neighbor denominators.

Stern-Brocot intervals enumerate all candidates once

The Stern-Brocot tree starts from the neighboring pair \(0/1 \lt 1/1\). A node stores one neighboring interval \((a/b,c/d)\), and its children are obtained from the mediant

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

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

The determinant invariant is preserved:

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

So every visited node is again a pair of Farey neighbors. Moreover, every positive reduced rational appears in exactly one interval of the Stern-Brocot tree, so every ambiguous midpoint has one unique node that generates it. This gives a one-to-one search space for counting.

Why the pruning rules are mathematically safe

For a current node \((a/b,c/d)\), the midpoint belongs to the answer exactly when

$\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right) \lt \frac{1}{100},$

which the implementations rewrite as the integer inequality

$ (ad+bc)\cdot 100 \lt 2bd. $

Two monotonicity properties justify pruning whole subtrees.

If \(bd \gt Q/2\), then the current midpoint denominator already exceeds \(Q\), and both children have strictly larger products, namely \(b(b+d)\) and \((b+d)d\). No descendant can come back under the limit.

If the left endpoint already satisfies \(a/b \ge 1/100\), then the entire interval lies at or above the threshold, and every descendant remains inside that interval. By contrast, a midpoint that is currently too large does not allow pruning by itself, because descendants closer to the left edge may still drop below \(1/100\).

Worked example

Consider the neighboring fractions

$\frac{1}{101} \lt \frac{2}{201},\qquad 101\cdot 2 - 1\cdot 201 = 1.$

Their midpoint is

$x=\frac{1}{2}\left(\frac{1}{101}+\frac{2}{201}\right)=\frac{403}{40602}\approx 0.0099256,$

so it lies below \(1/100\). The reduced denominator is exactly

$q=2\cdot 101\cdot 201=40602.$

Because \(1/101\) and \(2/201\) are Farey neighbors, no reduced fraction with denominator below \(101+201=302\) lies between them. Therefore any denominator bound \(B\) with \(201 \le B \lt 302\) makes these two fractions equally good best approximations, so \(403/40602\) is ambiguous. This is precisely the kind of midpoint counted by the algorithm.

How the Code Works

The C++, Python, and Java implementations represent one Stern-Brocot interval by four integers \(a,b,c,d\). They avoid floating-point arithmetic completely: the denominator test uses the product bound \(bd \le Q/2\), the threshold pruning compares \(a/b\) against \(1/100\) by cross-multiplication, and the midpoint test checks \((ad+bc)\cdot 100 \lt 2bd\).

The main search is an explicit depth-first traversal with a stack. When a node survives the pruning tests, the implementation forms the mediant \((a+c)/(b+d)\), pushes the two child intervals, and increments the answer if the midpoint itself satisfies the threshold. Because each Stern-Brocot node corresponds to exactly one neighboring Farey pair, each increment counts exactly one ambiguous rational.

The C++ and Java implementations add a parallel front end for the largest input. They first expand the tree breadth-first until they have a moderate frontier of seed intervals, count the ambiguous midpoints seen during that prefix expansion, and then distribute the remaining subtrees across worker threads. The Python implementation performs the same traversal and the same exact tests in a single serial pass.

Complexity Analysis

Let \(V\) be the number of Stern-Brocot intervals that are actually popped from the stack before pruning stops them. The serial algorithm runs in \(O(V)\) time, because each visited node performs only a constant amount of integer arithmetic and either terminates immediately or creates two children.

Memory usage is \(O(H)\) for the explicit stack, where \(H\) is the maximum search depth reached before pruning. In the parallel versions there is additional storage for the seed frontier, but total work remains linear in the number of visited nodes. The essential gain is structural: the search follows only Farey gaps whose midpoint denominator can still fit under \(10^8\) and whose interval has not moved entirely past \(1/100\), instead of scanning a gigantic set of unrelated rationals.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=198
2. Stern-Brocot tree: Wikipedia - Stern-Brocot tree
3. Farey sequence: Wikipedia - Farey sequence
4. Mediant: Wikipedia - Mediant
5. Best rational approximation: Wikipedia - Diophantine approximation