Project Euler 95: Find the smallest member of the longest amicable chain

---

Project Euler 95 Problem Description

Project Euler 95: 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 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

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.

Analysis

A very straightforward approach that follows a logical flow similar to problem 21 by sieving the sum of divisors instead of using a function to calculate them.
1. Sieve a set of divisors for all numbers up to the limit. Uses a bunch of memory which is a drawback to solving larger problems. But I can mostly guess what the answer is for 10⁹⁹ because things don’t really change much.
2. The easy part is to calculate successive members of the chain and slice it where the chain begins to repeat.
3. Collect the smallest member for each new increasing chain length.
4. Print out the results.

The easy way from learning by doing it the hard way:

Project Euler 95 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 95 Solution Python 2.7 source.

Real solution that helped show a pattern:

Project Euler 95 Solution

Runs < 2.8 seconds in Python 2.7.

Use this link to get the Project Euler 95 Solution Python 2.7 source.

Afterthoughts

• Wrapping program in a function cut time by 40%.