## Perfect, amicable and sociable numbers

### Introduction

For a number n, we define s(n) to be the sum of the aliquot parts of n, i.e., the sum of the positive divisors of n, excluding n itself: so, for example, s(8)=1+2+4=7, and s(12)=1+2+3+4+6=16. If we start at some number and apply s repeatedly, we will form a sequence:

s(15)=1+3+5=9,

s(9)=1+3=4,

s(4)=1+2=3,

s(3)=1,

s(1)=0.

If we ever reach 0, we must stop, since all integers divide 0. There are three obvious possibilities for the behavior of this aliquot sequence:

1. It can terminate at 0 like the example above.
2. It can fall into an aliquot cycle, of length 1 (a fixed point of s), 2, or greater.
3. It can grow without bound and approach infinity.

### Perfect numbers

A perfect number is a cycle of length 1 of s, i.e., a number whose positive divisors (except for itself) sum to itself. For example, 6 is perfect (1+2+3=6), and in fact 6 is the smallest perfect number. The next two perfect numbers are 28 (1+2+4+7+14=28) and 496 (1+2+4+8+16+31+62+124+248=496).

If 2p-1 is prime, then 2p-1(2p-1) is even and perfect, and conversely, all even perfect numbers have this form. Primes of the form 2p-1 are called Mersenne primes, so we can say that there are just as many even perfect numbers as Mersenne primes. It is conjectured that the number of Mersenne primes is infinite; if this is true there will also be an infinity of even perfect numbers. Also, there are just as many even perfect numbers known as Mersenne primes known (48 as of 4-II-2015.)

One of the oldest conjectures in mathematics that is still open is that there are no odd perfect numbers. It has been proved that any odd perfect number must exceed 10300 [BCT], and must be divisible by a prime power exceeding 1020 [COHG1987].

### Amicable numbers

An amicable pair is a cycle of length 2 of s, i.e., a pair of numbers each of which equals the sum of the other's aliquot parts; the members of amicable pairs are also called amicable. The smallest such pair is (220,284).

It is conjectured that there are infinitely many amicable pairs, although, as for perfect numbers, this is not known. Here is a list of all the amicable pairs with lower member below 2.01*1011, and here is a longer (but less annotated) list comprising the first 5001 amicable pairs. For bigger amicable pairs, see [TBBHL], or see the extensive database below.

### Sociable numbers

The members of aliquot cycles of length greater than 2 are often called sociable numbers. The smallest two such cycles have length 5 and 28, and were found early in the last century by Poulet [POU]. Borho [BOR1969] constructed one of length 4 in 1969. Everything since has been found via computer search. Here is a list of all the sociable numbers I know of.

### Aliquot sequences

In the introduction we divided aliquot sequences into three classes. Catalan [CAT] and Dickson [DIC] conjectured that all sequences fell into the first two classes, so that iterating s never approached infinity, regardless of the starting number. However, there is now good reason to believe [GUY1977] that iterating s does go to infinity for most even starting numbers, although this has not been proven for any starting number. The smallest starting number whose sequence has not been completely computed is 276.

### Related problems

By substituting some other function for s, we can construct various other classes of numbers. For example, if we set s+(n)=s(n)+1, the fixed points of s+ are called almost perfect or augmented perfect. All powers of 2 are almost perfect; no other almost perfect numbers are known. 2-cycles of s+ have been called augmented amicable pairs, and we can define augmented sociable numbers similarly. Here is a list of the 188 augmented amicable pairs with smaller member less than 109, and the two cycles of augmented sociable numbers that I know of. There are more augmented amicable pairs in the database below.

Similarly, if we set s-(n)=s(n)-1, we get quasi-perfect or reduced perfect numbers, reduced amicable or quasi-amicable numbers (also called betrothed numbers, because each number in the pair is the sum of the proper divisors of the other), and reduced sociable numbers. Quasi-perfect numbers must be odd squares above 1035 [HC]; none are known. Here is a list of the 180 pairs of reduced amicable numbers below 109, and the one cycle of reduced sociable numbers that I know of. There are more reduced amicable pairs in the database below.

### Other definitions of divisibility

We may generalize all these notions in various ways by changing the criterion we use to say when one number divides another. To start, we observe that if the prime factorization of n is p1a1 p2a2 ... pmam, then d divides n just when d can be written in the form p1c1 p2c2 ... pmcm, where c1 is between 0 and a1, inclusive, c2 is between 0 and a2, inclusive, and so on.

To generalize the notion of divisibility, we change the relation that the cis must have to the ais. If each ci equals 0 or ai, we call d a unitary divisor of n. If each ci is between 0 and ai, and, if ai is even, ci does not equal ai/2, then d is a bi-unitary divisor of n. If each ci divides the corresponding ai, then d is called an exponential divisor of n [STR]. If each ci+1 divides the corresponding ai+1, then I call d a modified exponential divisor of n. Finally, d is called an infinitary divisor of n if each ci has a zero bit in its binary expansion everywhere that the corresponding ai does [COHG1990].

After making all these definitions, we can talk about reduced bi-unitary amicable numbers, augmented infinitary sociable numbers, and so on and so forth. There are some obvious relations between these notions. For example, if all members of an aliquot cycle are not divisible by the square of any prime, or squarefree, it is also a unitary aliquot cycle. The following table, compiled February 2015, shows how many of each of these types of generalized aliquot cycles exist.

Augmented, reduced or normal? Type of divisor Code Perfect numbers Amicable pairs Cycles of length >2
Normal Normal n. >10 (including all numbers 2p-1(2p-1), where 2p-1 is prime) >107 >102
Unitary u. >=5 [WAL1975] >106 >102
Bi-unitary b. 3 [WAL1972] >105 >102
Infinitary i. >102 >107 >103
Modified exponential e. >10 >106 >102
Exponential E. Infinitely many of each; see below
Augmented Normal n+ Infinitely many (including all powers of 2) >103 >=1
Unitary u+ 2 (1 and 2) [BN] >10 ?
Bi-unitary b+ Infinitely many (1 and all numbers 22k+1; see below) >102 ?
Infinitary i+ Infinitely many (all numbers 22k-1; see below) >102 ?
Modified exponential e+ 2 (1 and 2) >10 ?
Exponential E+ 1 (1) ? ?
Reduced Normal n- ? >103 >=1
Unitary u- 0 [BN] >10 ?
Bi-unitary b- 0 >102 ?
Infinitary i- 0 >102 ?
Modified exponential e- 0 >10 ?
Exponential E- 0 ? ?

Some of the numbers in the table have simple explanations:

If t is the sum of generalized divisors of an augmented or reduced generalized perfect number, then either t=2n+1 or t=2n-1, so t is odd and t and n are relatively prime. However the sum of unitary divisors, bi-unitary divisors, or infinitary divisors of a number is always even, unless the number is a power of 2. Therefore, there are no reduced unitary perfect numbers, and, apart from 1 and 2, no augmented unitary perfect numbers [BN]; there are no reduced bi-unitary perfect numbers and, apart from 1 and numbers of the form 22k+1, no augmented bi-unitary perfect numbers; and there are no reduced infinitary perfect numbers and, apart from numbers of the form 22k-1, no augmented infinitary perfect numbers. For similar reasons, there are no reduced modified exponential perfect numbers, and, apart from 1 and 2, no augmented modified exponential perfect numbers. Also, any prime factor of a number also divides any exponential divisor of that number, so except for 1, which is augmented exponential perfect but not reduced exponential perfect, there cannot be any augmented or reduced exponential perfect numbers.

The most interesting question about these generalizations is whether there exist an infinite number of unitary perfect numbers. At present, just five are known [WAL1975]. There are known to be exactly three bi-unitary perfect numbers [WAL1972].

Here is a list of all generalized aliquot cycles, defined as above, with member preceding the largest member less than 2*1011. The exponential cycles are not listed, as they can be easily computed from the modified exponential cycles. Each cycle is preceded by its codes, from the `Code' column of the table above, and its length. For example, a line n+b+i+4 would mean that the following cycle is of length 4, and is an augmented aliquot cycle, augmented bi-unitary aliquot cycle, and augmented infinitary aliquot cycle.

### Database of aliquot cycles

Jan Otto Munch Pedersen used to have a database of aliquot cycles and generalized aliquot cycles, Tables of Aliquot Cycles, available on line, at the URL http://amicable.homepage.dk/tables.htm. It included discoverer information for each cycle. Unfortunately, it doesn't seem to be available any more, so I am providing most of the data from this database here. The data is current as of the last time Pedersen's database was updated, which was on Oct. 1, 2007.

### A short bibliography

[GUY1994] gives many more references. Wolfgang Creyaufmueller has a page on aliquot sequences.

[ALA] J. Alanen, O. Ore, and J. G. Stemple, Systematic computations on amicable numbers, Math. Comp. 21 (1967), 242-245.

[BH] W. Borho and H. Hoffmann, Breeding amicable numbers in abundance, Math. Comp. 46 (1986), 281-293.

[BRA] P. Bratley, F. Lunnon, and J. McKay, Amicable numbers and their distribution, Math. Comp. 24 (1970), 431-432.

Gives a computer-generated proof that all odd perfect numbers must exceed 10160.
Extends the proof in [BC] to give a proof that all odd perfect numbers must exceed 10300.
Full text available, in TeX (3K), DVI (4K), Postscript (121K), or PDF (70K).
[COH] H. Cohen, On amicable and sociable numbers, Math. Comp. 24 (1970), 423-429.

[COS1977] P. Costello, Amicable pairs of Euler's first form, J. Rec. Math. 10 (1977-1978), 183-189.

[COS1991] P. Costello, Amicable pairs of the form (i,1), Math. Comp. 56 (1991), 859-865.

[ERD1955] P. Erdös, On amicable numbers, Publ. Math. Debrecen 4 (1955-1956), 108-111.

Proves that as n goes to infinity, A(n)/n goes to zero, where A(n) is the number of amicable pairs with larger member below n.

[ERD1976] P. Erdös, On asymptotic properties of aliquot sequences, Math. Comp. 30 (1976), 641-645.

[FLA] A. Flammenkamp, New sociable numbers, Math. Comp. 56 (1991), 871-873.

[GUY1994] R. K. Guy, Unsolved problems in number theory (Springer-Verlag, 1994.)

[HC] P. Hagis and G. L. Cohen, Some results concerning quasiperfect numbers, J. Australian Math. Soc. Series A, 33 (1982), 275-286.

[LEE] E. J. Lee, Amicable numbers and the bilinear diophantine equation, Math. Comp. 22 (1968), 181-187.

[LM] E. J. Lee and J. S. Madachy, The history and discovery of amicable numbers, J. Rec. Math. 5 (1972); part 1, 77-93; part 2, 153-173; part 3, 231-249.

[MOE1] D. Moews and P. C. Moews, A search for aliquot cycles below 1010, Math. Comp. 57 (1991), 849-855.

[MOE2] D. Moews and P. C. Moews, A search for aliquot cycles and amicable pairs, Math. Comp. 61 (1993), 935-938.

[POM] C. Pomerance, On the distribution of amicable numbers, J. reine angew. Math., 293/294 (1977) 217-222; II 325 (1981) 183-188.

This paper runs as follows:

Si l'on considère un nombre entier a, la somme b de ses parties aliquotes, la somme c des parties aliquotes de b, la somme d des parties aliquotes de c et ainsi de suite, on obtient un développement qui, poussé indéfiniment, peut se présenter sous trois aspects différents:

1. Le plus souvent on finit par tomber sur un nombre premier, puis sur l'unité. Le développement est fini.
2. On retrouve à un moment donné un nombre déjà rencontré. Le développement est indéfini et périodique. Si la période n'a qu'un terme, ce terme est un nombre parfait. Si la période a deux termes, ces termes sont des nombres amiables. La période peut avoir plus de deux termes, qu'on pourrait appeler, pour garder la même terminologie, des nombres sociables. Par exemple le nombre 12496 engendre une période de 4 termes, le nombre 14316 une période de 28 termes.
3. Enfin dans certains cas, on arrive à des nombres très grands qui rendent le calcul insupportable. Exemple: le nombre 138.

Cela étant, je demande:

1. Si ce troisième cas existe réellement ou si, en poursuivant indéfiniment le calcul, il ne se résoudrait pas nécessairement dans l'un ou l'autre des deux premiers, comme je suis porté à le croire.
2. Si l'on connaît d'autres groupes sociables que ceux donnés plus haut, notamment des groupes de trois termes. (Il est inutile, je pense, d'essayer les nombres inférieurs à 12000 que j'ai tous examinés.) P. POULET.

[STR] E. G. Straus and M. V. Subbarao, On exponential divisors, Duke Math. J. 41 (1974), 465-471.

[TR1984] H. J. J. te Riele, On generating new amicable pairs from given amicable pairs, Math. Comp. 42 (1984), 219-223.

[TR1986] H. J. J. te Riele, Computation of all the amicable pairs below 1010, Math. Comp. 47 (1986), 361-368.

[TR1994] H. J. J. te Riele, A new method for finding amicable pairs; pp. 577-581 in Mathematics of Computation 1943-1993, Proc. Symp. Appl. Math. 43 (1994), Amer. Math. Soc., Providence, RI.

[TBBHL] H. J. J. te Riele, W. Borho, S. Battiato, H. Hoffman, and E. J. Lee, Table of Amicable Pairs between 1010 and 1052, Centrum voor Wiskunde en Informatica, Note NM-N8603, Stichting Math. Centrum, Amsterdam, 1986.

[WAL1972] C. R. Wall, Bi-unitary perfect numbers, Proc. Amer. Math. Soc. 33 (1972), 39-42.

[WAL1975] C. R. Wall, The fifth unitary perfect number, Canad. Math. Bull. 18 (1975), 115-122.

### Technical appendix

First, if g is some generalized definition of divisibility, let Sg(n) be the sum of g-divisors of n. We have defined generalized divisibility so that if the prime factorization of n is p1a1 p2a2 ... pmam, then Sg(n)= Sg(p1a1) Sg(p2a2) ... Sg(pmam). We can now prove various facts we used above.

Now if p is odd, the sum of the modified exponential divisors of pe will have the same parity as the number of divisors of e+1, so it will be even unless e+1 is a square. But if n is augmented or reduced modified exponential perfect, then Smodified exponential (n) must be odd, so n must have the prime factorization 2a p1b1-1 ... pmbm-1, where a may be zero, p1, ..., pm are distinct odd primes, and b1, ..., bm are squares exceeding 1. Now if a>0, Smodified exponential(2a)/2a will be 3/2 if a=1, 5/4 if a=2, and by the last paragraph, no bigger than 3/2 otherwise. Since each bi is a square exceeding 1, each bi is at least 4, so Smodified exponential(pibi-1)/pibi-1 is no bigger than 7/6 if pi=3, or (1-pi-2)-5/4 otherwise. But the product of (1-q-2)-1 over all primes q is the sum of the reciprocals of the squares of the positive integers, which is pi2/6, so the product taken over all primes except 2 and 3 is (pi2/6)/((4/3)(9/8)). Therefore, Smodified exponential(n)/n is no bigger than (3/2)(7/6)((pi2/6)/((4/3)(9/8)))5/4, which is less than 1.965, so any reduced modified exponential perfect number n would have to satisfy 2n+1< 1.965n, which is obviously impossible. Any augmented modified exponential perfect number n must satisfy 2n-1<1.965n, so n must be one of the positive integers between 1 and 28. But of all these integers, only 1 and 2 are augmented modified exponential perfect.

Last significant revision 8-II-2015