This is another Project Euler challenge that I initially solved by try and error and some help from Dr. Google. A little Wikipedia research (German only) reveals the correct result without the necessity of writing any line of code.

Nevertheless, I tried to implement a solution. Currently, I am down to a one-minute runtime, which is way too slow. But it’s the best algorithm I could come up with at the moment. Therefore it is time to wrap up.

First, I implemented a function to retrieve all proper divisors of a given number and calculate their sum. This was one of the first areas of my code which I could optimize. Let’s take the number 12 for example. Its proper divisors are 1, 2, 3, 4, and 6. Instead of determining each divisor individually, a little trick can be applied. Once you know that 2 is a proper divisor of 12 you know immediately that the number 6 is a proper divisor as well. The same is true for 3, which pairs with 4. Only half the work to be done.

Now it was time to generate number chains. I chose to use a simple for-loop to kick off each chain, followed by a while-block to make it grow. But to what upper limit? The problem description states that no element of the list must exceed 1.000.000. It turns out that the first number that yields a sum of its proper divisors, which exceeds this limit is 327.600. To be on the safe side, I decided to set the upper limit to 350.000. As the solution to Problem 95 is a way smaller number my assumption seems to be faulty. But I lack the math skills to come up with a better idea.

Next, I did some research on potential chains. It looks like every chain “terminates” somehow.

Using a while-loop to grow each chain, what are the cases I will encounter?

Case 1: The chain terminates with 1.
Example: 10 → 8 → 7 → 1

Case 2: It’s a perfect number.
Example: 6 → 6

Case 3: It’s an amciable pair.
Example: 284 → 220 → 284

Case 4: It’s an amicable chain. That’s what I’m looking for.
Example: As stated in the problem description, 12496 → 14288 → 15472 → 14536 → 14264 → 12496 

Case 5: It does not start as an amicable chain but turns into one.
Example: 562 → 284 → 220 → 284 (see Case 3)

I tried to optimize by keeping a list of “dead ends”. For example, once I know that 10 results in a useless chain, I store it. Whenever I come across 10 one more time, I can abort immediately. Over time my “dead ends” keep growing, and I can abort more and more chains. This comes with the cost of having to check this list.

That’s it. Create chains plus a couple of assertions.
Abort when discovering…

• …the number 1 (Case 1)
• …a perfect number (Case 2)
• …an amicable pair (Case 3)
• …an amicable chain (Case 4)
• …a “pseudo” amicable chain (Case 5)
• …a number above 1.000.000
• …a “dead end”

Store the longest chain and return its starting point as a solution to Problem 95.

As written above, my implementation has a runtime of roughly one minute. This is a strong indication that I must have missed something. But at the moment, I have no idea how to further improve my code. Now that I know the problem solution, I decreased the upper limit of my for-loop as a trial, which yields the correct result in a single second.

So, I might return to Problem 95 in the future.