I know of no practical use for Amicable numbers, but they’re rather fun. And rare. But let’s start with a definition. Let 
with 
Now we’re ready to define amicable numbers!
Amicable numbers: Two numbers, are amicable, if, and only if, and .
Given , we can find and test if . But to do that efficiently, we need to compute (or ) very rapidly. The first expression above requires , but we can do much better. Let’s see how.
Let’s start with . Or, more precisely, with with a prime number. With a prime number, we have the special case:
because, since it’s prime, it can only have 1 and as divisors, therefore, . What about , an integer power of a prime number? We have:
because, since can only be divided by powers of . OK, that’s cute, but that’s still a special case. How does that help us solving the general case, ? Well, we can observe that if isn’t a prime (nor a power of a prime) then it’s of the form
,
where the are the multiplicities. That is, if , we can rewrite it as , and the multiplicities are , and the . We then have that:
.
Yes! Look at that incredible inversion of the product and ! This mean we can compute much faster than just testing the divisors one by one, but we need the prime decomposition of . Well, that’s not too bad, because testing for primes up to takes (because numbers less than are prime, and we need to test only up to ).
What is the speed-up? Well, pretty good actually. For the first million numbers, we have 0.47s (on the usual box, i7 2600k) for the factorization plus the product- formula, against 50-something minutes for the naïve algorithm.
*
* *
We are now set to start trying enumerating amicable numbers. Using a computer, it should not be too hard, but until Euler—methinks—only two or three pairs were known: (220, 284), since the Ancient Greeks, one other pair, not sure which, and (9363584, 9437056), found by an Iranian scholar in the 16th century. Today, we know a lot of them, but it’s still a challenge to write an efficient program to enumerate them. We now have the first piece, satisfactorily completed (since even will prove problematic for really, really big numbers).
To be continued…
Filed under: algorithms, Mathematics Tagged: amicable numbers, Ancient Greeks, Euler, Factorization, number theory, Prime numbers
