Problem Analysis
This problem concerns the Farey sequence F_N: the ascending list of all reduced proper fractions n/d with 0 < n < d ≤ N and greatest common divisor gcd(n, d) = 1. "Reduced" means numerator and denominator share no common factor; "proper" means the fraction lies strictly between 0 and 1. I am asked for the numerator of the fraction immediately to the left of 3/7 when N = 1,000,000.
A literal reading invites an O(N) scan: for each denominator d up to N, compute the largest n/d still below 3/7 and keep the closest. But the Farey sequence has an adjacency property that makes the loop unnecessary. The gap 3/7 - n/d equals (3d - 7n)/(7d). To push n/d as close to 3/7 as possible from below, I want this gap as small as possible and positive - meaning the numerator 3d - 7n should equal the smallest positive integer, 1, while the denominator d is as large as the bound permits. This is precisely the Stern-Brocot neighbour condition |aq - bp| = 1 for two adjacent fractions a/b and p/q. Setting 3d - 7n = 1 with d = 7k forces n = 3k - 1, and the gap becomes 1/(7k), minimised by taking k as large as possible: k = floor(N / 7). The entire search collapses to a handful of arithmetic operations, giving an O(1) solution (treating the GCD reduction of two bounded integers as constant time).
Solution Approach
Direct Farey-neighbour formula (Python and C)
Both files implement the same closed-form derivation and differ only in language idiom.
Step 1 - compute k. I take k = floor(N / 7) (max_d // 7 in Python, max_d / 7 in C, which is integer division for integral operands). This is the largest k satisfying 7k ≤ N. I deliberately use a denominator that is a multiple of 7 because the target 3/7 has denominator 7, and the Farey adjacency condition 3d - 7n = 1 only yields an integer n when d is a multiple of 7.
Step 2 - form the candidate. With d = 7k and n = 3k - 1, the fraction (3k - 1)/(7k) sits exactly 1/(7k) below 3/7. Because k is maximal, 1/(7k) is the smallest gap attainable, so no fraction with denominator ≤ N can squeeze between it and 3/7 - this is the immediate left neighbour.
Step 3 - reduce and report the numerator. The pair (3k - 1, 7k) may share a common factor, so I divide both by their GCD before reading off the numerator. In Python I express the whole derivation as fractions.Fraction(3, 7) - fractions.Fraction(1, 7 * (max_d // 7)); the Fraction constructor reduces automatically, and I simply return result.numerator. In C there is no built-in rational type, so I write an explicit iterative gcd using the Euclidean algorithm, divide the numerator by it, and format the result.
The language-specific difference worth noting is integer width. Python's integers are arbitrary precision, so the extra test with N = 10^12 (where 7k approaches 7 x 10^12) is handled transparently. In C I use long long - at least 64 bits, with a signed maximum near 9.2 x 10^18 - so that both 7k and 3k - 1 stay well within range and never overflow silently.