Problem Analysis
I am asked to count the reduced proper fractions n/d - fractions with n < d and gcd(n, d) = 1 - that lie strictly between 1/3 and 1/2 when the denominator is bounded by some maximum D (here D = 12000). The natural setting is the Farey sequence F_D: the ordered list of every reduced fraction in [0, 1] whose denominator is at most D. Two structural facts about Farey sequences make this tractable without ever factoring anything. First, the mediant property: if a/b and c/d are adjacent in some F_n, the first fraction to appear between them as n grows is their mediant (a + c)/(b + d). Second, the neighbour identity: adjacent fractions a/b and c/d satisfy bc - ad = 1. These two facts let me walk the interval (1/3, 1/2) one fraction at a time.
There is a faster, completely different angle: counting by rank. The rank of a fraction p/q in F_D is its position - the number of reduced fractions in [0, 1] with denominator at most D that do not exceed p/q. If I can compute rank(1/2) and rank(1/3) cheaply, the answer is simply rank(1/2) - rank(1/3) - 1 (the -1 removes 1/2 itself, which is a boundary and not counted). A rank reduces to counting coprime pairs, which is exactly the job of Mobius inversion implemented as a divisor sieve. That yields an O(D log D) algorithm. The two enumeration approaches, by contrast, do O(1) work per counted fraction and therefore run in O(answer) time, which grows like O(D^2). At D = 12000 the answer is about 7.3 million; at D = 100000 it is about 500 million - which is precisely why the sieve wins so decisively.
Solution Approach
Algorithm s0: Iterative Farey Neighbour Traversal
This approach (p0073_s0.py and p0073_s0.c) walks the Farey sequence one fraction at a time using the neighbour recurrence. Given two consecutive fractions whose denominators are prev_d and d, the denominator of the next one is d_next = D - ((D + prev_d) mod d). This formula follows directly from the neighbour identity bc - ad = 1 combined with the requirement that the next denominator be as large as possible while staying at most D. The crucial simplification is that I track only denominators. Both boundary fractions 1/3 and 1/2 have numerator 1, and once the boundaries are fixed, the mediant structure forces every intermediate numerator uniquely - so the numerators carry no information and I drop them entirely.
The traversal starts at the fraction just above 1/3 with the largest denominator at most D. That denominator is 2 + 3 * floor((D - 2) / 3) - the largest value of the form 2 + 3k not exceeding D - and its predecessor in the walk is 1/3, denominator 3. The loop counts one fraction per iteration and stops when d reaches 2, the denominator of the upper boundary 1/2, which is not counted. Each step is O(1), so the total cost is O(answer). The Python and C versions are line-for-line equivalent; at D = 12000 the C version runs in 0.0247 s against 0.3569 s for Python, a roughly 14x speedup purely from compilation.
Algorithm s1: Stern-Brocot Recursive Mediant Search
This approach (p0073_s1.py and p0073_s1.c) enumerates the same fractions but via the recursive structure of the Stern-Brocot tree. Given lower and upper boundaries with denominators b_lo and b_hi, their mediant has denominator b_lo + b_hi. If that sum exceeds D, no fraction with a small enough denominator lies between the boundaries and the function returns 0. Otherwise the mediant is one counted fraction, and I recurse into the two sub-intervals (lower, mediant) and (mediant, upper). The initial call is recursion(3, 2) because the boundaries are 1/3 and 1/2 and, as in s0, only denominators matter.
This is correct and elegant, but it generates one recursive call per counted fraction plus the failing leaves, so it too runs in O(answer) time with O(depth) stack usage. The C version stores D in a file-scope variable g_max_d to avoid threading it through every call. The Python version raises the recursion limit to 10^6, since the tree can become very deep at large D. Interestingly, the Python recursion is the slowest of all approaches at scale (48.98 s at D = 100000) because of Python's per-call overhead and lack of tail-call optimisation; in C, however, the recursion (0.8119 s) beats the iterator (1.7096 s) at the same scale.
Algorithm s2: Mobius Sieve Rank Computation
This is the fast algorithm (p0073_s2.py and p0073_s2.c). I define rank(n, d) as the number of reduced fractions with denominator at most D that are at most n/d, and return rank(1, 2) - rank(1, 3) - 1. To compute a rank, I first build an array where data[i] = floor(i * n / d). At this point data[i] counts all fractions k/i (for k from 1 to floor(i*n/d)), including the ones not in lowest terms. To isolate the reduced fractions of each exact denominator, I run an additive sieve: for each i, I subtract data[i] from every multiple data[j] with j = 2i, 3i, .... This is Mobius inversion expressed as repeated subtraction: it strips out the contribution of fractions that share a common factor with their denominator, leaving data[i] equal to the count of fractions in lowest terms with denominator exactly i that are at most n/d. Summing the array gives the rank.
The inner loop visits D/i elements for each i, and the sum of D/i over all i is the harmonic series, which is O(log D). The total work is therefore O(D log D) with O(D) memory. The C version allocates the array with malloc and uses long long to keep the running sum safely in range; the Python version builds the array with a list comprehension. This algorithm completes in 0.0028 s (C) and 0.1095 s (Python) at D = 100000 - the only approaches comfortable at that scale.