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. Bibliography
  9. 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 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 (44 as of 28-IX-2006.)

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, Jan Otto Munch Pedersen has a very extensive list of amicable pairs online; also, see [TBBHL].

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.

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 betrothed numbers below 109, and the one cycle of reduced sociable numbers that I know of.

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 May 2001, 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) >106 >102
Unitary u. >=5 [WAL1975] >105 >102
Bi-unitary b. 3 [WAL1972] >105 >102
Infinitary i. >102 >105 >103
Modified exponential e. >10 >105 >102
Exponential E. Infinitely many of each; see below
Augmented Normal n+ Infinitely many (including all powers of 2) >102 >=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- ? >102 >=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:

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

A short bibliography

[GUY1994] gives many more references; also, see Jan Otto Munch Pedersen's online tables. 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 10160.

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

[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 (45K), or PDF (56K).
[COH] H. Cohen, On amicable and sociable numbers, Math. Comp. 24 (1970), 423-429.

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

[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à recontré. 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 la 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 seuis porté à le croire.
  2. Si l'on connait d'autres groupes sociables que ceux donnés plus haut, notament 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.

1. For all prime powers pe where e>0, Sunitary(pe)=pe+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 pe where e>0, Sbi-unitary(pe) 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 pe where e>0, write e as a sum of distinct powers of 2, so that e =2b1+2b2+... +2bn, say. Then Sinfinitary(pe)= (p2b1+1) ... (p2bn+1) , so Sinfinitary(pe) 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=2m, then Sg(n) <= Snormal(n)= 2m+1-1=2n-1, so n cannot be reduced g-perfect, and n will be augmented g-perfect just when all divisors of 2m are also g-divisors of 2m. 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 pe where e>0, Smodified exponential(pe)= 1+...+pd-1+...+pe, 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+p2+...+p(e+1)/q-1+ pe, which is no bigger than p(e-1)/2(1-p-1)-1+ pe. Therefore, Smodified exponential(pe)/pe 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 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.

Back to the home page.

David Moews (dmoews@fastmail.fm)

Last significant revision 30-XII-2010