notes.html

problem 74 · 32 lines

<article>
<h3>Problem Analysis</h3>
<p>
The engine of this problem is a single deterministic rule: from any positive integer <code>n</code>, the successor is the sum of the factorials of its decimal digits, so <code>145 -&gt; 1! + 4! + 5! = 145</code>. Iterating this rule traces a path through the integers, and because every integer has exactly one successor, the structure is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Functional_graph" rel="noopener noreferrer" target="_blank">functional graph</a> - a directed graph in which every node has out-degree exactly one. A fundamental property of any functional graph on a finite set is that every trajectory eventually enters a cycle: there are only finitely many reachable values, so by the <a class="reference-source" href="https://en.wikipedia.org/wiki/Pigeonhole_principle" rel="noopener noreferrer" target="_blank">pigeonhole principle</a> some value must repeat, and once it does the path loops forever. The <em>chain</em> the problem asks about is the count of distinct values visited before the first repetition. Our task is to count how many starting numbers below one million produce a chain of exactly sixty distinct terms.
</p>
<p>
Two observations make this tractable. First, the state space is tightly bounded. The digit factorials are fixed constants - the largest is <code>9! = 362880</code> - so any 7-digit number maps to at most <code>7 x 362880 = 2540160</code>. Every value we ever encounter, even for starting numbers up to ten million, stays below about 2.5 million, so a flat array of three million slots covers the entire universe of reachable values. Second, because each value has a single fixed successor, two paths that ever meet stay merged forever. This means each value's chain length can be computed once and reused - the defining condition for <a class="reference-source" href="https://en.wikipedia.org/wiki/Memoization" rel="noopener noreferrer" target="_blank">memoization</a>. Without caching, the cost is roughly O(N x L), where N is the limit and L the maximum chain length (sixty here); with caching, the amortised cost per starting number falls toward O(1), giving an effectively linear O(N) algorithm.
</p>
<h3>Solution Approach</h3>
<h4>Algorithm 0 - Walk-and-cache storing only chain lengths (p0074_s0.py and p0074_s0.c)</h4>
<p>
This is the most direct <a class="reference-source" href="https://en.wikipedia.org/wiki/Memoization" rel="noopener noreferrer" target="_blank">memoization</a> strategy and the fastest of the three. For each starting number I walk forward along the successor map, appending each value to a <code>seen</code> list, and stop as soon as one of two things happens: either the current value is already in <code>seen</code> (the walk has closed a cycle entirely within itself), or the current value is already in the cache (we have reached a value whose chain length is already known). At that point the total length of the chain beginning at <code>seen[0]</code> is fully determined: it is <code>len(seen)</code> plus the cached length of the value we stopped on, or just <code>len(seen)</code> if we closed a cycle.
</p>
<p>
The decisive step is the back-propagation pass. Once I know the chain length of the first node, every node on the walk has a known length too: <code>seen[i]</code> has length <code>total - i</code>, because it sits exactly <code>i</code> steps further along the same chain. A single backward loop fills the cache for every node visited, so the work this walk performed benefits every future walk that ever touches one of these nodes. This is precisely the flattening idea behind <a class="reference-source" href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Path_compression" rel="noopener noreferrer" target="_blank">path compression</a> in union-find structures: collapse a whole traversal into the cache in one go.
</p>
<p>
The Python version (<code>p0074_s0.py</code>) uses two dictionaries: <code>chain_length_cache</code> mapping a value to its chain length, and <code>graph</code> mapping a value to its precomputed successor so the digit-factorial sum is never recomputed. The C version (<code>p0074_s0.c</code>) replaces both dictionaries with flat <code>int</code> arrays of size three million, using <code>0</code> as the "not yet computed" sentinel. Cycle detection during the walk is a simple linear scan over <code>seen</code>; this looks like an O(L) operation, but L is bounded near sixty, so it costs at most a few dozen comparisons per step - cheaper in practice than maintaining a hash set. At N = 1,000,000 the C version runs in 0.0160 s and the Python version in 0.9436 s.
</p>
<h4>Algorithm 1 - Walk-and-cache storing full chain lists (p0074_s1.py and p0074_s1.c)</h4>
<p>
Algorithm 1 stores, in Python, the actual list of values that make up each chain rather than just its length. The function <code>add_chains</code> builds a <code>current_chain</code> list and a <code>visited</code> set. When the walk reaches a value already in the cache, it splices the cached list onto the current chain with <code>list.extend</code>; when it reaches a value already in <code>visited</code>, it has found a self-contained cycle. Each previously unseen node is then assigned the appropriate tail slice of <code>current_chain</code>. This is conceptually clean and supports visualisation - you can print an entire chain - but it allocates a fresh list slice for every cached node, which is expensive. In Python it runs in 2.6839 s at N = 1,000,000, roughly three times slower than Algorithm 0's 0.9436 s.
</p>
<p>
The C translation (<code>p0074_s1.c</code>) recognises that storing the full list is unnecessary: only the lengths are needed for the answer. It therefore keeps a single <code>chain_length</code> array, exactly like Algorithm 0, and reconstructs the same length information from each value's position index in <code>current_chain</code>. The one structural difference from s0 is that s1's C code uses a boolean <code>visited_flag</code> array - cleared after each walk via a tracked <code>visited_list</code> - for O(1) cycle-membership testing, instead of s0's linear scan. This extra bookkeeping is why s1_c is marginally slower than s0_c (0.0185 s vs 0.0160 s at N = 1,000,000).
</p>
<h4>Algorithm 2 - Visualisation variant of Algorithm 1 (p0074_s2.py and p0074_s2.c)</h4>
<p>
Algorithm 2 is functionally identical to Algorithm 1; it lives in a separate file purely to add optional coloured terminal output gated behind the <code>--show</code> flag. The Python file (<code>p0074_s2.py</code>) adds a <code>ColorCodes</code> enum of ANSI escape sequences and a <code>print_chains</code> function that renders each chain with its cycle entry highlighted. The C translation (<code>p0074_s2.c</code>) drops the visualisation entirely and is therefore essentially identical to s1_c. Its benchmarks track s1 closely across every input size (0.0214 s vs 0.0185 s in C, 2.6254 s vs 2.6839 s in Python at N = 1,000,000).
</p>
</article>