Perfect, amicable and sociable numbers

(how to have fun summing up divisors)

Contents

1. Introduction
2. Perfect numbers
3. Amicable numbers
4. Sociable numbers
5. Aliquot sequences
6. Related problems
7. Other definitions of divisibility
8. Database of aliquot cycles
9. Bibliography
10. Technical appendix

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 2^p-1 is prime, then 2^p-1(2^p-1) is even and perfect, and conversely, all even perfect numbers have this form. Primes of the form 2^p-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 10³⁰⁰ [BCT], and must be divisible by a prime power exceeding 10²⁰ [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*10¹¹, 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 10⁹, 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 10³⁵ [HC]; none are known. Here is a list of the 180 pairs of reduced amicable numbers below 10⁹, 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 p₁^a₁ p₂^a₂ ... p_m^a_m, then d divides n just when d can be written in the form p₁^c₁ p₂^c₂ ... p_m^c_m, where c₁ is between 0 and a₁, inclusive, c₂ is between 0 and a₂, inclusive, and so on.

To generalize the notion of divisibility, we change the relation that the c_is must have to the a_is. If each c_i equals 0 or a_i, we call d a unitary divisor of n. If each c_i is between 0 and a_i, and, if a_i is even, c_i does not equal a_i/2, then d is a bi-unitary divisor of n. If each c_i divides the corresponding a_i, then d is called an exponential divisor of n [STR]. If each c_i+1 divides the corresponding a_i+1, then I call d a modified exponential divisor of n. Finally, d is called an infinitary divisor of n if each c_i has a zero bit in its binary expansion everywhere that the corresponding a_i 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.

Some of the numbers in the table have simple explanations:

Two numbers are called relatively prime when there is no number exceeding 1 which divides them both. If f is the greatest squarefree number which divides the product of all members of a generalized aliquot cycle, then multiplying each member of the cycle by f will change a modified exponential aliquot cycle to an exponential aliquot cycle. Also, an exponential aliquot cycle will remain an exponential aliquot cycle when each member of the cycle is multiplied by a squarefree number relatively prime to every member of the cycle, so there are an infinite number of exponential perfect numbers, of exponential amicable pairs, and of exponential sociable numbers. In fact, every exponential aliquot cycle can be obtained by starting with some modified exponential aliquot cycle and following these two steps, so looking at the number of modified exponential aliquot cycles is more interesting than looking at the number of exponential aliquot cycles.

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 2^2k+1, no augmented bi-unitary perfect numbers; and there are no reduced infinitary perfect numbers and, apart from numbers of the form 2^2k-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*10¹¹. 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.

[BN] W. E. Beck and R. M. Najar, Fixed points of certain arithmetic functions, Fibonacci Quarterly, 15 (1977), 337-342.

[BOR1969] W. Borho, �ber die Fixpunkte der k-fach iterierten Teilersummenfunktion, Mitt. Math. Gesellsch. Hamburg, 9 (1969), 34-48.

[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.

[BC] R. P. Brent and G. L. Cohen, A new lower bound for odd perfect numbers, Math. Comp. 53 (1989), 431-437.

Gives a computer-generated proof that all odd perfect numbers must exceed 10¹⁶⁰.

[BCT] R. P. Brent, G. L. Cohen, and H. J. J. te Riele, Improved techniques for lower bounds for odd perfect numbers, Math. Comp. 57 (1991), 857-868.

Extends the proof in [BC] to give a proof that all odd perfect numbers must exceed 10³⁰⁰.

[CAT] E. Catalan, Propositions et questions diverses, Bull. Soc. Math. de France 16 (1887-88), 128-129.

Full text available, in TeX (3K), DVI (4K), Postscript (121K), or PDF (70K).

[COHG1987] G. L. Cohen, On the largest component of an odd perfect number, J. Australian Math. Soc. Series A, 42 (1987), 280-286.

[COHG1990] G. L. Cohen, On an integer's infinitary divisors, Math. Comp. 54 (1990), 395-411.

[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.

[DIC] L. E. Dickson, Theorems and tables on the sum of the divisors of a number, Quarterly J. Math. 44 (1913), 264-296.

[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.

[GUY1977] R. K. Guy, Aliquot sequences, in Number Theory and Algebra (Academic Press, 1977.)

[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 10¹⁰, 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.

[POU] P. Poulet, #4865, L'interm�diare des math. 25 (1918), 100-101.

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 10¹⁰, 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 10¹⁰ and 10⁵², 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 S_g(n) be the sum of g-divisors of n. We have defined generalized divisibility so that if the prime factorization of n is p₁^a₁ p₂^a₂ ... p_m^a_m, then S_g(n)= S_g(p₁^a₁) S_g(p₂^a₂) ... S_g(p_m^a_m). We can now prove various facts we used above.

1. For all prime powers p^e where e>0, S_unitary(p^e)=p^e+1. Unless p=2, this will be even, so any number divisible by a prime other than 2 will have its sum of unitary divisors even.

2. For all prime powers p^e where e>0, S_bi-unitary(p^e) will be the sum of e+1 powers of p, if e is odd, or e powers of p, if e is even. In either case, it is the sum of an even number of powers of p, so it will be even unless p=2, and any number divisible by a prime other than 2 will have its sum of bi-unitary divisors even.

3. For all prime powers p^e where e>0, write e as a sum of distinct powers of 2, so that e =2^b₁+2^b₂+... +2^b_n, say. Then S_infinitary(p^e)= (p^2b₁+1) ... (p^2b_n+1) , so S_infinitary(p^e) will be even unless p=2, and any number divisible by a prime other than 2 will have its sum of infinitary divisors even.

4. From 1, 2, and 3, we already know that any augmented or reduced unitary, bi-unitary or infinitary perfect number must be a power of 2. However, if g is `unitary', `bi-unitary', or `exponential', and n=2^m, then S_g(n) <= S_normal(n)= 2^m+1-1=2n-1, so n cannot be reduced g-perfect, and n will be augmented g-perfect just when all divisors of 2^m are also g-divisors of 2^m. This will happen just when m=0 or m=1 for unitary divisors; when m=0 or m is odd for bi-unitary divisors; or when m is 1 less than a power of 2 for infinitary divisors.

5. For all prime powers p^e where e>0, S_{modified exponential}(p^e)= 1+...+p^d-1+...+p^e, where the sum is over all divisors d of e+1. If q is the smallest divisor exceeding 1 of e+1, then (e+1)/q will be the largest divisor less than e+1 of e+1, so this sum will be no bigger than 1+p+p²+...+p^(e+1)/q-1+ p^e, which is no bigger than p^(e-1)/2(1-p^-1)^-1+ p^e. Therefore, S_{modified exponential}(p^e)/p^e is no bigger than 1+(1-p^-1)^-1p^-(e+1)/2, and if e>=3, this will be no bigger than 1+(1-p^-1)^-1p^-2, which is 3/2 if p=2, 7/6 if p=3, and no bigger than 1+(5/4)p^-2< (1-p^-2)^-5/4 otherwise.

Now if p is odd, the sum of the modified exponential divisors of p^e 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 S_{modified exponential} (n) must be odd, so n must have the prime factorization 2^a p₁^b₁-1 ... p_m^b_m-1, where a may be zero, p₁, ..., p_m are distinct odd primes, and b₁, ..., b_m are squares exceeding 1. Now if a>0, S_{modified exponential}(2^a)/2^a 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 b_i is a square exceeding 1, each b_i is at least 4, so S_{modified exponential}(p_i^b_i-1)/p_i^b_i-1 is no bigger than 7/6 if p_i=3, or (1-p_i^-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 pi²/6, so the product taken over all primes except 2 and 3 is (pi²/6)/((4/3)(9/8)). Therefore, S_{modified exponential}(n)/n is no bigger than (3/2)(7/6)((pi²/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.

Back to the home page.

David Moews ([email protected])

Last significant revision 8-II-2015