notes.html

problem 14 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
The <a class="reference-source" href="https://en.wikipedia.org/wiki/Collatz_conjecture" rel="noopener noreferrer" target="_blank">Collatz sequence</a> follows a deceptively simple rule: halve an even number, otherwise triple it and add one. The <a class="reference-source" href="https://en.wikipedia.org/wiki/Collatz_conjecture" rel="noopener noreferrer" target="_blank">Collatz conjecture</a> - 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.
</p>
<p>
The structural observation that unlocks the problem is that the chain-length function has <a class="reference-source" href="https://en.wikipedia.org/wiki/Overlapping_subproblems" rel="noopener noreferrer" target="_blank">overlapping subproblems</a>: once the length from some intermediate value <code>n</code> is known, it can be reused by every other chain that passes through <code>n</code>. That is precisely the condition under which <a class="reference-source" href="https://en.wikipedia.org/wiki/Memoization" rel="noopener noreferrer" target="_blank">memoization</a> - a form of <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> 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 <code>x</code> at or below <code>limit / 2</code>, the value <code>2x</code> is still within the limit, and its chain is the chain from <code>x</code> with one extra step prepended - so <code>2x</code> always has the strictly longer chain and a lower-half <code>x</code> can never win. The argument stops exactly where <code>2x</code> would leave the range, which is why the cut-off is <code>limit / 2</code> rather than any larger bound. With <a class="reference-source" href="https://en.wikipedia.org/wiki/Memoization" rel="noopener noreferrer" target="_blank">memoization</a>, 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.
</p>
<h3>Solution Approach</h3>
<h4>Memoised Recursive Collatz (Solution 0 - Python and C)</h4>
<p>
Both languages run one algorithm. Its heart is a function <code>collatz_length(n)</code> returning the number of terms from <code>n</code> down to 1: the base case <code>n == 1</code> has length 1, and otherwise the length is one more than the length of the next value - <code>n / 2</code> when even, <code>3n + 1</code> when odd. This is a direct transcription of the mathematical recurrence, made efficient purely by caching.
</p>
<p>
The Python version defines <code>collatz_length</code> as a nested function decorated with <a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.lru_cache" rel="noopener noreferrer" target="_blank">functools.lru_cache</a>, so the cache is a fresh <a class="reference-source" href="https://en.wikipedia.org/wiki/Hash_table" rel="noopener noreferrer" target="_blank">hash table</a> created on every call to <code>solve</code>. This is deliberate: the benchmark harness calls <code>solve</code> 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 <code>solve</code> means each timed run rebuilds the table from scratch and reports an honest figure. Python's arbitrary-precision integers mean <code>3n + 1</code> can never overflow, so value ranges are a non-issue.
</p>
<p>
The C version allocates a flat array of <code>long long</code> indexed by <code>n</code> with <a class="reference-source" href="https://en.cppreference.com/w/c/memory/calloc" rel="noopener noreferrer" target="_blank">calloc</a>, using the value 0 as a "not yet computed" <a class="reference-source" href="https://en.wikipedia.org/wiki/Sentinel_value" rel="noopener noreferrer" target="_blank">sentinel value</a>. Because <code>3n + 1</code> 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 <code>solve</code>, 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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Hash_table" rel="noopener noreferrer" target="_blank">hash table</a> deliberately: indexing a flat block benefits from CPU <a class="reference-source" href="https://en.wikipedia.org/wiki/Locality_of_reference" rel="noopener noreferrer" target="_blank">locality of reference</a> and avoids per-lookup hashing overhead.
</p>
<p>
In both versions the search loop starts at <code>max_number</code> and walks down only to just above <code>max_number // 2</code> (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.
</p>
</article>