Problem Analysis
At heart this problem asks me to find the longest cycle in a functional graph - a directed graph in which every node has exactly one outgoing edge. Here the edge from n points to s(n), the sum of n's proper divisors (every divisor of n except n 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 perfect number is a cycle of length 1, an amicable pair 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.
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 additive sieve - a generalisation of the Sieve of Eratosthenes - in O(N log N) time. Second, a functional graph 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.
Solution Approach
Additive Sieve plus Path-Tracking Cycle Detection (Python and C)
Both files implement the same two-phase algorithm, so I describe them together and flag where they diverge.
Phase 1 - build the divisor-sum array. I allocate divisor_sum[0..N] initialised to zero. For each integer i from 1 to N/2 I add i to every multiple of i in the range [2i, N]. This is the additive sieve pattern: rather than asking "what are the divisors of n?", I iterate over each candidate divisor i and push its contribution outward to all its multiples. The inner loop runs N/i times for each i, so the total work is the harmonic sum N/2 + N/3 + ... = O(N log N). When the sieve finishes, divisor_sum[n] holds s(n) - exactly the edge function of our graph.
Phase 2 - cycle detection by walking the graph. I scan every number from 1 to N. If a number is already classified, I skip it. Otherwise I follow the edges - repeatedly applying divisor_sum - 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).
In the Python solution I track the current walk with a list path (for ordered traversal) and a set ch (for O(1) membership testing). The walk halts when c falls out of range or is already in ch. If the terminating node c equals the start i, the whole path is a cycle. I then store every node in the seen 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 i. This is safe precisely because I iterate i upward: any cycle reachable through a tail will eventually have its own smallest member visited directly as i, at which point the condition c == i fires and the smallest member is simply i itself.
The C solution is more general. I use an in_path array that stores the 1-indexed position of each node in the current walk (0 means "not in this walk"), which lets me detect mid-path cycles. If the walk terminates at a node c already in the path but not equal to i, the cycle begins at in_path[c] - 1 and has length path_len - cycle_start_pos. Nodes before that position are tail nodes, which I mark with seen = -1 ("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 in_path only for the nodes actually touched, keeping cleanup proportional to the walk length rather than O(N).