Again something I haven’t even heard of before. What the hell are “amicable numbers”?

I had to read the problem twice to understand what it is about. And I had absolutely no idea how to tackle this problem. But as always:

• brute force solutions are stupid
• let’s do some research first

Therefore I went over to Wolfram MathWorld for more information on amicable pairs.

The first thing I noticed was that amicable pairs are not that common. At least according to my definition of “common”. The given example of 220 and 284 actually is the first known pair. Below 10.000 only five pairs exist:

• (220, 284)
• (1184, 1210)
• (2620, 2924)
• (5020, 5564)
• (6232, 6368)

Add these up and you’ve got the solution to the problem.

But how to calculate pairs of amicable numbers?

Rules for producing amicable pairs include the Thâbit ibn Kurrah rule rediscovered by Fermat and Descartes and extended by Euler to Euler’s rule. A further extension not previously noticed was discovered by Borho (1972).

(Wolfram MathWorld)

Thâbit ibn Kurrah Rule

Thâbit ibn Kurrah’s rules is a beautiful result of Thâbit ibn Kurrah dating back to the tenth century […].

(Wolfram MathWorld)

Wait…did I just read “dating back to the tenth century”? Holy…!

So how to apply this rule? I have to be pragmatic here, my math skills are enough to tackle the “how” but unfortunately not the “why”.

Let’s pick a number n equal to or greater than two. The rule presents us with three equations:

For n = 2: h = 11, t = 5 and s = 71. Three prime numbers.

Actually h, t and s have to be prime! Otherwise the following formula to calculate an amicable pair is not applicable.

But in case h, t and s are prime, the formula to calculate an amicable pair is:

In case of n = 2:

Which is the first pair (220, 284).

What about n = 3, n = 4 and so on?

For n = 3: h = 23, t = 11 and s = 287. Unfortunately 287 is not prime as it is divisible by 7. No amicable pair can be constructed for n = 3.

For n = 4: h = 47, t = 23 and s = 1151. All three are prime numbers. Therefore a pair of amicable numbers exists, which is (17296, 18416).

But now with the number 17.296 I am  already above the given limit of 10.000. So apparently just applying Thâbit ibn Kurrah’s rule is not sufficient to solve this problem.

Euler’s rule

Euler’s rule is a generalization of Thâbit ibn Kurrah’s rule. Let’s see if this one does the trick.

in case p, q and r are all prime numbers…

…and m satisfies the following condition…

…amicable pairs are constructed using this formula:

Let’s check for m = 1 and n = 2: p = 5, q = 11, r = 71. All prime, which leads to the already known amicable pair of (220, 284). So far so good.

I can now increase either only n, or m and n.

m = 2, n = 3: r = 287 which is not prime. No amicable pair exists here.
m = 3, n = 4: Amicable pair exists (17296, 18416). But I am already above 10.000.
m = 1, n = 3: p = 9 which is not prime. No amicable pair.
m = 1, n = 4: q = 143 which is not prime. No amicable pair. And I am again already above 10.000.

So what to do now? Stuck.