## Amicable Numbers (part I)

I know of no practical use for Amicable numbers, but they’re rather fun. And rare. But let’s start with a definition. Let $n$ be a natural number (a positive integer), and let

$\displaystyle \sigma(n)=\sum_{d|n}d$

with $d \in \mathbb{N}$ and $1\leqslant{d}\leqslant{n}$, be the sum of the divisors of $n$. We’re in fact interested in the sum of the proper divisors of $n$, that is,

$s(n)=\sigma(n)-n$

Now we’re ready to define amicable numbers!

Amicable numbers: Two numbers, $n, m \in \mathbb{N}$ are amicable, if, and only if, $s(n)=m$ and $s(m)=n$.

Given $n$, we can find $m=s(n)$ and test if $n=s(m)=s(s(n))$. But to do that efficiently, we need to compute $s(n)$ (or $\sigma(n)$) very rapidly. The first expression above requires $O(n)$, but we can do much better. Let’s see how.

Let’s start with $\sigma(n)$. Or, more precisely, with $\sigma(p)$ with $p$ a prime number. With $p$ a prime number, we have the special case:

$\sigma(p)=1+p$

because, since it’s prime, it can only have 1 and $p$ as divisors, therefore, $\sigma(p)=1+p$. What about $\sigma(p^a)$, an integer power of a prime number? We have:

$\displaystyle\sigma(p^a)=1+p+p^2+\cdots+p^{a-1}+p^a=\frac{p^{a+1}-1}{p-1}$

because, since $p^a$ can only be divided by powers of $p$. OK, that’s cute, but that’s still a special case. How does that help us solving the general case, $\sigma(n)$? Well, we can observe that if $n$ isn’t a prime (nor a power of a prime) then it’s of the form

$\displaystyle n = p_1^{m_1} \cdot p_2^{m_2} \cdot p_k^{m_k}=\prod_{i=1}^k p_i^{m_i}$,

where the $m_i$ are the multiplicities. That is, if $n=2^2 \cdot 5 \cdot 7$, we can rewrite it as $n=2^2\cdot 5^1 \cdot 7^1$, and the multiplicities are $m=\{2,1,1\}$, and the $p=\{2,5,7\}$. We then have that:

$\displaystyle\sigma(n)=\sigma\left(\prod_{i=1}^k p_i^{m_k}\right)=\prod_{i=1}^k \sigma(p_i^{m_i})$.

Yes! Look at that incredible inversion of the product and $\sigma(\cdot)$! This mean we can compute $\sigma(n)$ much faster than just testing the divisors one by one, but we need the prime decomposition of $n$. Well, that’s not too bad, because testing for primes up to $O(\sqrt{n})$ takes $O(\frac{\sqrt{n}}{\ln n})$ (because $O(\frac{n}{\ln n})$ numbers less than $n$ are prime, and we need to test only up to $O(\sqrt{n})$).

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-$\sigma$ 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, $s(n)=\sigma(n)-n$ satisfactorily completed (since even $O(\frac{\sqrt{n}}{\ln n})$ will prove problematic for really, really big numbers).

To be continued…