notes.html

problem 95 · 13 lines

<article>
<h3>Problem Analysis</h3>
<p>At heart this problem asks me to find the longest cycle in 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 exactly one outgoing edge. Here the edge from <code>n</code> points to <code>s(n)</code>, the sum of <code>n</code>'s <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisor#Definition" rel="noopener noreferrer" target="_blank">proper divisors</a> (every divisor of <code>n</code> except <code>n</code> itself). An "amicable chain" is precisely a cycle in this graph: a run of distinct numbers each mapping to the next, with the last looping back to the first. A <a class="reference-source" href="https://en.wikipedia.org/wiki/Perfect_number" rel="noopener noreferrer" target="_blank">perfect number</a> is a cycle of length 1, an <a class="reference-source" href="https://en.wikipedia.org/wiki/Amicable_numbers" rel="noopener noreferrer" target="_blank">amicable pair</a> is a cycle of length 2, and the problem hunts longer ones. I want the smallest member of the longest cycle whose elements all stay at or below one million.</p>
<p>Two observations make this tractable. First, instead of factoring each of the million numbers separately (which costs roughly O(N√N)), I can compute every divisor sum in one pass with an <strong>additive sieve</strong> - a generalisation of the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a> - in O(N log N) time. Second, a <a class="reference-source" href="https://en.wikipedia.org/wiki/Functional_graph" rel="noopener noreferrer" target="_blank">functional graph</a> always decomposes into "rho"-shaped pieces: a tail of nodes leading into a single cycle. That structure lets me classify every node with a linear scan that walks each chain once, marking nodes as I go so I never reprocess them. The total cost is O(N log N), dominated by the sieve, with O(N) space.</p>
<h3>Solution Approach</h3>
<h4>Additive Sieve plus Path-Tracking Cycle Detection (Python and C)</h4>
<p>Both files implement the same two-phase algorithm, so I describe them together and flag where they diverge.</p>
<p><strong>Phase 1 - build the divisor-sum array.</strong> I allocate <code>divisor_sum[0..N]</code> initialised to zero. For each integer <code>i</code> from 1 to N/2 I add <code>i</code> to every multiple of <code>i</code> in the range [2i, N]. This is the additive sieve pattern: rather than asking "what are the divisors of <code>n</code>?", I iterate over each candidate divisor <code>i</code> and push its contribution outward to all its multiples. The inner loop runs N/i times for each <code>i</code>, so the total work is the harmonic sum N/2 + N/3 + ... = O(N log N). When the sieve finishes, <code>divisor_sum[n]</code> holds <code>s(n)</code> - exactly the edge function of our graph.</p>
<p><strong>Phase 2 - cycle detection by walking the graph.</strong> I scan every number from 1 to N. If a number is already classified, I skip it. Otherwise I follow the edges - repeatedly applying <code>divisor_sum</code> - until one of three things happens: the next value leaves the valid range [1, N] (no cycle can survive because chain members must not exceed one million), I land on a node classified in a prior walk, or I revisit a node in the current walk (a cycle has closed).</p>
<p>In the Python solution I track the current walk with a list <code>path</code> (for ordered traversal) and a set <code>ch</code> (for O(1) membership testing). The walk halts when <code>c</code> falls out of range or is already in <code>ch</code>. If the terminating node <code>c</code> equals the start <code>i</code>, the whole path is a cycle. I then store every node in the <code>seen</code> dictionary with that cycle's length and update the answer if this is the longest chain yet. The Python code only records cycles whose closing node equals <code>i</code>. This is safe precisely because I iterate <code>i</code> upward: any cycle reachable through a tail will eventually have its own smallest member visited directly as <code>i</code>, at which point the condition <code>c == i</code> fires and the smallest member is simply <code>i</code> itself.</p>
<p>The C solution is more general. I use an <code>in_path</code> array that stores the 1-indexed position of each node in the current walk (0 means "not in this walk"), which lets me detect <em>mid-path</em> cycles. If the walk terminates at a node <code>c</code> already in the path but not equal to <code>i</code>, the cycle begins at <code>in_path[c] - 1</code> and has length <code>path_len - cycle_start_pos</code>. Nodes before that position are tail nodes, which I mark with <code>seen = -1</code> ("visited but not a cycle member") so they are never reprocessed; cycle nodes get the cycle length. When a cycle is the new longest, I scan its members to find the minimum, the safe and general way to report the smallest element. After every walk I reset <code>in_path</code> only for the nodes actually touched, keeping cleanup proportional to the walk length rather than O(N).</p>
</article>