Problem Analysis
The number sqrt(2) admits a representation as an infinite continued fraction - an expression formed by repeatedly nesting a term of the shape 1/(2 + 1/(2 + ...)). Truncating that infinite nesting after a finite number of levels yields a rational approximation called a convergent. The task is to count, among the first thousand convergents, how many have a numerator whose number of decimal digits strictly exceeds that of the denominator.
The observation that makes this tractable is that consecutive convergents are linked by a clean two-variable recurrence relation. If the current convergent is p/q, the next one is (p + 2q)/(p + q). This follows directly from the structure of the expansion: adding one more level wraps the previous fraction as 1 + 1/(1 + p/q), and that algebraic substitution sends the pair (p, q) to (p + 2q, p + q). The fractions in the problem - 3/2, 7/5, 17/12, 41/29, 99/70, ... - all satisfy this map exactly. Because the recurrence is built from nothing but addition, I can generate every convergent with exact integer arithmetic, never touching division or floating point. The price is growth: p and q grow by roughly a factor of 1 + sqrt(2) per step, so after n steps they carry on the order of n digits and require arbitrary-precision integers ("bignums"). Each step is dominated by adding two D-digit numbers where D grows linearly with the index, so the total cost is the sum 1 + 2 + ... + n, giving overall complexity of O(n^2).
Solution Approach
Iterative Convergent Recurrence with Big Integers
Both the Python and C solutions implement the same algorithm: hold the current numerator and denominator as arbitrary-precision integers, apply the map (p, q) -> (p + 2q, p + q) once per expansion, and increment a counter on every step where p has more decimal digits than q.
I seed both variables at 1. This represents the state just before the first expansion: applying the recurrence relation once gives numerator 1 + 2*1 = 3 and denominator 1 + 1 = 2, that is, the fraction 3/2 - exactly the problem's first expansion. The critical subtlety is that the two updates must be simultaneous: the new numerator depends on the *old* denominator, and the new denominator depends on the *old* numerator. I must compute both new values before overwriting either, or I corrupt the second update with the first.
In Python, arbitrary-precision integers are built into the language, so the loop body is a single tuple assignment numerator, denominator = (numerator + 2 * denominator, numerator + denominator). To compare magnitudes I convert each integer to its decimal string and compare lengths. That is O(D) per comparison but trivially correct. I also guard the comparison against Python 3.11+'s cap on int-to-string conversion, lifting the limit with sys.set_int_max_str_digits(0) only if the ValueError actually fires.
In C there is no native bignum, so I built a small base-10^9 big-integer type: a fixed-size array of 32-bit limbs stored little-endian (least-significant limb at index 0), each limb holding up to nine decimal digits. Two helpers do the arithmetic - bi_add_twice computes b + 2c (the numerator update) and bi_add computes b + c (the denominator update), both propagating carries across limbs. The choice of base 10^9 pays off in bi_decimal_digits: every limb except the topmost contributes exactly nine digits, so the digit count is 9*(size - 1) plus a short loop over the most-significant limb. I preallocated MAX_LIMBS = 512 slots - far more than the roughly 50 limbs needed even at 10000 expansions - so the hot loop performs no heap allocation.