Problem Analysis
Every quadratic irrational - including the square root of any non-square integer - has a continued fraction expansion that is eventually periodic. A continued fraction writes a number as an integer part plus the reciprocal of another such expansion, nested indefinitely; for square roots this nesting settles into a repeating block. My task is to count how many N up to 10,000 have an odd-length repeating block. Perfect squares are excluded outright: their roots are rational, the expansion terminates, and worse, the recurrence below would divide by zero on the first step.
The key observation that makes the problem tractable is that the algorithm for extracting the coefficients - the standard square-root periodic continued fraction recurrence - keeps the entire state in three small integers. At each step the current remainder has the form (sqrt(N) + m) / d, and from (m, d) I read off the next coefficient a. Crucially m is bounded by sqrt(N) and d divides N - m^2 exactly, so the triple (m, d, a) ranges over a finite set. By the pigeonhole principle, the sequence of triples must eventually repeat, and the first repeat closes the cycle: the number of distinct triples seen is the period. Since the period for N up to 10,000 is at most a few hundred, each inner loop runs in roughly O(sqrt(N)) steps, and the overall cost is about O(N_max * sqrt(N_max)) - on the order of 10^6 integer operations, trivially fast.
Solution Approach
Continued-Fraction Period Detection via State-Triple Cycle
Both the Python (p0064_s0.py) and C (p0064_s0.c) files implement the identical algorithm; I describe it once and note the language differences afterward.
Step 1 - Compute a0. For each candidate N I compute a0 = floor(sqrt(N)). If a0^2 == N then N is a perfect square and I skip it. Filtering these at the call site keeps the period routine's precondition - its input is irrational - explicit, and avoids the division-by-zero the recurrence would otherwise hit.
Step 2 - Iterate the recurrence. Starting from m = 0, d = 1, a = a0, I repeatedly apply three integer updates: m = d*a - m, then d = (N - m*m) / d, then a = (a0 + m) / d. It is a provable fact about this periodic continued fraction recurrence that d always divides N - m^2 exactly, so every quantity stays an integer - no floating point appears inside the loop, and there is no rounding error to reason about.
Step 3 - Detect the period. I accumulate the visited triples. When a freshly computed triple already appears in the collection, the cycle has closed, and the period is the count of triples gathered before that repeat. I test against every stored triple rather than only the initial state. In practice the cycle here always begins immediately at the first generated triple, but the general membership check costs nothing in clarity and is the robust, correct cycle-detection condition.
Step 4 - Count odd periods. The outer loop runs over every non-square N from 2 to the limit, calls the period routine, and tallies each odd result.
Language differences. The Python version stores triples in a list of tuples and tests membership with the in operator - O(period) per check, which is negligible because periods are tiny. It uses math.isqrt for an exact integer square root inside the routine, and filters squares with not math.sqrt(n).is_integer(). The C version stores triples in a dynamically allocated array of int[3], starting at capacity 64 and doubling via realloc. Because C's sqrt operates on double, I wrap each call in two corrective while loops to guarantee an exact integer floor. Both produce 1322 for N up to 10,000; the C build runs in about 0.0062 s against 0.0940 s for Python, roughly a 15x speedup.