Problem Analysis
The Collatz sequence follows a deceptively simple rule: halve an even number, otherwise triple it and add one. The Collatz conjecture - verified computationally for vast ranges but still unproven - holds that every positive integer eventually reaches 1. The task is to find the starting value below one million whose chain has the most terms. The naive approach iterates over every start and counts its steps independently, but this repeats enormous amounts of work, because distinct chains converge and then share a long common tail down to 1.
The structural observation that unlocks the problem is that the chain-length function has overlapping subproblems: once the length from some intermediate value n is known, it can be reused by every other chain that passes through n. That is precisely the condition under which memoization - a form of dynamic programming that caches the result of each subproblem the first time it is solved - pays off. A second, subtler observation prunes the search: only starts above half the limit need be tried. For any x at or below limit / 2, the value 2x is still within the limit, and its chain is the chain from x with one extra step prepended - so 2x always has the strictly longer chain and a lower-half x can never win. The argument stops exactly where 2x would leave the range, which is why the cut-off is limit / 2 rather than any larger bound. With memoization, each value contributes only a handful of new steps before landing on a cached entry, giving an overall cost of roughly O(N log N) for a limit of N.
Solution Approach
Memoised Recursive Collatz (Solution 0 - Python and C)
Both languages run one algorithm. Its heart is a function collatz_length(n) returning the number of terms from n down to 1: the base case n == 1 has length 1, and otherwise the length is one more than the length of the next value - n / 2 when even, 3n + 1 when odd. This is a direct transcription of the mathematical recurrence, made efficient purely by caching.
The Python version defines collatz_length as a nested function decorated with functools.lru_cache, so the cache is a fresh hash table created on every call to solve. This is deliberate: the benchmark harness calls solve repeatedly, and a cache built once at import (or shared across calls) would leave only the first call paying for it and make every later call almost free, understating the true cost. Building it inside solve means each timed run rebuilds the table from scratch and reports an honest figure. Python's arbitrary-precision integers mean 3n + 1 can never overflow, so value ranges are a non-issue.
The C version allocates a flat array of long long indexed by n with calloc, using the value 0 as a "not yet computed" sentinel value. Because 3n + 1 can exceed the limit, the recursion computes any out-of-range value without caching it; the result still bubbles up correctly, and the first in-range value on the way back up is cached. The array is allocated and freed inside solve, mirroring the Python cache's per-call lifetime so the two benchmarks are measured on the same footing. A contiguous array is chosen over a hash table deliberately: indexing a flat block benefits from CPU locality of reference and avoids per-lookup hashing overhead.
In both versions the search loop starts at max_number and walks down only to just above max_number // 2 (integer halving in both languages). As argued above, any maximum-length chain must begin in this upper half, so the lower half is skipped entirely. A running pair of variables tracks the best length and its starting number, updated whenever a new record appears.