I know of no practical use for Amicable numbers, but they’re rather fun. And rare. But let’s start with a definition. Let be a natural number (a positive integer), and let
with and , be the sum of the divisors of . We’re in fact interested in the sum of the proper divisors of , that is,
Now we’re ready to define amicable numbers!
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…