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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: