Amicable Chains

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of $28$ are $1$, $2$, $4$, $7$, and $14$. As the sum of these divisors is equal to $28$, we call it a perfect number.
Interestingly the sum of the proper divisors of $220$ is $284$ and the sum of the proper divisors of $284$ is $220$, forming a chain of two numbers. For this reason, $220$ and $284$ are called an amicable pair.
Perhaps less well known are longer chains. For example, starting with $12496$, we form a chain of five numbers:
$$12496 \to 14288 \to 15472 \to 14536 \to 14264 (\to 12496 \to \cdots)$$
Since this chain returns to its starting point, it is called an amicable chain.
Find the smallest member of the longest amicable chain with no element exceeding one million.

This problem involves a lot of calculations, so a solution within this text interface may not be suitable. However, I can outline a general approach on how you could solve it programmatically:

1. **Creating a reference of divisor sums up to one million**: First you would create a list, or another structure, of the sums of proper divisors for each number up to one million.

This is an imperative first step and requires you understanding how to find divisors. The divisors of a number are formed by pairs whose product equals the number. If you have a number `n`, and you find a number `a` that divides `n`, then there must be a corresponding number `b` where `a*b` equals `n`. The numbers `a` and `b` are the pair of divisors.

You iterate from `1` to the square root of `n` and for every number `a` that divides `n`, you add both `a` and the corresponding `b` (which is `n/a`) to the sum. One special case to consider is when `n` is a perfect square. Both `a` and `b` would equal the square root of `n`, but since it’s a proper divisor, you should only add it once to the sum.

Now that you have the sum of divisors for all numbers up to `1 million`, you’re good to move to Step 2

2. **Iterating over each number and forming chains**: For each number `n` from `1` to `1 million`, you would form a chain. The chain starts with `n`, and the next number in the chain is the sum of proper divisors of `n`. You keep on adding numbers to the chain until you either hit a number that you have already added in the chain (in which case you check if it’s the smallest number in the chain), or hit a number outside the `1 million` limit.

If you reached the starting number after a chain of other numbers, that is an amicable chain. If the starting number is the smallest in the chain, then you compare the length of this chain to the longest found so far and update that if required.

3. **Finding the smallest member of the longest amicable chain**: You compare and store the smallest member in the longest amicable chain encountered so far. At the end of the program, this stored member is your answer.

As you can probably see, this is a heavy computational task that’s more suited to a programming solution.

For the solution using Python or another similar high-level programming language: first, you build the array of divisor sums. Then you iterate over all numbers from `1` to one million, following each chain to its end (either returning to the start, or exceeding one million), storing the smallest member and length of the longest chain seen.

Going through the above steps, programming and executing the solution, you’ll find that the smallest member of the longest amicable chain with no element exceeding one million is `14,316`.

More Answers: