# Let $(n, m)$, $n < m$ be an Amicable Pair. Looking for large sets of integers that cannot be $n$.

I've got a Python script that grinds out Amicable Pairs by trying out each integer: $i, i+1, i+2,\ldots$ . I've now found all APs with $1 \leq n \leq 65,000,000$. At this point I'm finding that it takes $24$ minutes per each additional million. To get into much larger $n$ I'll need to find a way to filter out substantial numbers of $n$ in advance. Have any been discovered?

My list of the first 202 APs: http://tutoree7.pastebin.com/dpEc0RbZ

-
Amicable pairs are studied in the literature as period two aliquot sequences, so using that keyword might point you to some relevant literature. –  Qiaochu Yuan Nov 20 '10 at 11:32
I actually recently just did a very similar thing with Gaussian integers in Sage, and even for smallish ones (norms around 20,000) it was taking a very long time, so I was wondering if I could rule things out in that case. –  Matt Nov 20 '10 at 19:23

Starting off by giving advice that does not seem to directly answer your question, you could do worse than to look at a few of the papers that bound the number of amicable numbers, particularly Erdos' 1955 paper showing that the density of amicable number is 0. This paper, is simple, direct, and largely the inspiration of what follows. Also worth looking at are Carl Pomerance's pair of papers giving better bounds. These papers are considerably more difficult than the Erdos paper, and at least for me, less applicable to inspiring good code. There is also a pair of papers by Erdos on $\sigma(n)/n$ that I found particularly illuminating, but I cannot find them (my wife may have a point about the state of my office.)

More directly relevant is H. J. J. te Riele's paper on the search for amicable numbers less than $10^{10}$

Now to more practical algorithmic suggestions. The ideas that follow, along with the details for testing that $\sigma(n)=m$ sketched here are responsible for most of the known amicable pairs between $10^{11}$ and $2^{64}$.

First, you only want to search for the smaller member of each amicable pair, this allows you to ignore numbers you know will not be abundant, and as around 3/4 of all numbers are not abundant this can speed things dramatically.

The main idea is to forget that the integers are well ordered (pinheaded enumerationist propaganda) and search through the integers in the range you are interested in by building them up by their prime factorization, essentially a tree traversal. This has many advantages, computing $\sigma(n)$ becomes trivial, and you can prune away large branches of non abundant numbers (I'll let you work out the details). Doing this efficiently makes a very good coding exercise.

The other opportunity for dramatic pruning comes from noting that if $n | m$ and $m>n$ then $n/\sigma(n) > m/\sigma(m)$, and that if $(a,b)$ is an amicable pair then $a/\sigma(a) + b/\sigma(b) = 1$ and that if $(a,b)$ is an amicable pair and $n | a$ then $\gcd(n,\sigma(n)) |b$. So if we let $m=\gcd(n,\sigma(n))$ then if $n/\sigma(n) + m/\sigma(m)<1$ no number of the form $nk$ where $k$ is relatively prime to $n$ can be an amicable number. This seems like a lot of work, but abundant numbers tend to have lots of small factors so most abundant numbers fail this test. Heuristically it appears that the number of 'candidates' that remain is on the order of approximately $x/\log x$.

Using these techniques you should be able to compute the pairs less than $10^{10}$ in under an hour on a fast machine (coding in C).

-

Your list of the first 202 Amicable Number pairs... seems to have omitted the pair (356408, 399592). If you check this pair, I think you'll find it belongs in the list of *203) pairs with the smallest number of the pair less than 66,000,000.

-