Amicable Pairs

I have always been fascinated by numbers and their properties and how they are related to one another. During my student life I have spent hundreds of hours reading about different properties of numbers, implementing algorithms to find these numbers for myself and optimizing these algorithms to be faster as I moved to bigger numbers with more digits.

One such special group of numbers is Amicable numbers. Amicable numbers are two different numbers related in such a way that the sum of their proper divisors is equal to the other number.

Let us give some definitions for better understanding later on:

For any natural number $n \in \mathbb{N}$ the sum of divisors $\sigma(n)$ is given as

Here $d$ is all the numbers that properly divide $n$. Let us take an example for $n = 6$, we have $\sigma(6) = 1 + 2 + 3 + 6 = 12$.

Sum of proper divisors is given as

Working with the previous example of $n=6$, we get

One nice thing about prime numbers is that $\sigma(p) = p + 1$.

Now that we know, how to compute sum of proper divisors, we can define when two numbers are amicable pairs.

Let $a \in \mathbb{N}$ and $b \in \mathbb{N}$, then $a$ and $b$ are called amicable pairs if and only if, the following is true:

In other words we can write:

The smallest amicable pairs are (220, 284) known to us since 1860. There is a database of known amicable pairs at 2 in Reference.

There are many open questions about amicable pairs:

• Are there infinitely many amicable pairs?
• Is there an efficient implementation to identify such numbers?

If you might have not noticed, computation of $s(n)$ or $\sigma(n)$ requires a lot of computation power if we want to find bigger amicable pairs. This is because we would need to identify the prime factorization of the numbers.

Any number $a$ can be represented as a product of the prime numbers. Let us take another example of $n = 12$. We can represent this number as $n = 2^2 \times 3$.

In other words let us take all prime numbers in a set $P$ such that $p_i \in P$, if and only if $p_i | n$ and $j_i = \argmax_k \left( p_i ^k | n \right)$, so $j_i$ is the maximum power of the prime $p_i$ that still divides $n$ without any remainders. Then we can write $n$ as following:

Then we can write following:

Let us have a look at an example:

and we see that

I have a paper, that I should some day finish which gives some properties of amicable numbers not mentioned above which can then be used to find them using methods not being used at the moment. Hopefully soon!

References

1. Amicable numbers on Wikipedia
2. Database of Amicable Pairs