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:
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 (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 10^{300} [BCT], and must be divisible by a prime power exceeding 10^{20} [COHG1987].
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^{11}, 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].
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.
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.
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^{9}, 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 10^{35} [HC]; none are known. Here is a list of the 180 pairs of betrothed numbers below 10^{9}, and the one cycle of reduced sociable numbers that I know of.
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_{1}^{a1} p_{2}^{a2} ... p_{m}^{am}, then d divides n just when d can be written in the form p_{1}^{c1} p_{2}^{c2} ... p_{m}^{cm}, where c_{1} is between 0 and a_{1}, inclusive, c_{2} is between 0 and a_{2}, inclusive, and so on.
To generalize the notion of divisibility, we change the relation that the c_{i}s must have to the a_{i}s. 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 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 2^{p-1}(2^{p}-1), where 2^{p}-1 is prime) | >10^{6} | >10^{2} |
Unitary | u. | >=5 [WAL1975] | >10^{5} | >10^{2} | |
Bi-unitary | b. | 3 [WAL1972] | >10^{5} | >10^{2} | |
Infinitary | i. | >10^{2} | >10^{5} | >10^{3} | |
Modified exponential | e. | >10 | >10^{5} | >10^{2} | |
Exponential | E. | Infinitely many of each; see below | |||
Augmented | Normal | n+ | Infinitely many (including all powers of 2) | >10^{2} | >=1 |
Unitary | u+ | 2 (1 and 2) [BN] | >10 | ? | |
Bi-unitary | b+ | Infinitely many (1 and all numbers 2^{2k+1}; see below) | >10^{2} | ? | |
Infinitary | i+ | Infinitely many (all numbers 2^{2k-1}; see below) | >10^{2} | ? | |
Modified exponential | e+ | 2 (1 and 2) | >10 | ? | |
Exponential | E+ | 1 (1) | ? | ? | |
Reduced | Normal | n- | ? | >10^{2} | >=1 |
Unitary | u- | 0 [BN] | >10 | ? | |
Bi-unitary | b- | 0 | >10^{2} | ? | |
Infinitary | i- | 0 | >10^{2} | ? | |
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 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^{11}. 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.
[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.
[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 10^{160}.
Extends the proof in [BC] to give a proof that all odd perfect numbers must exceed 10^{300}.
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.
[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.
[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^{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:
Cela étant, je demande:
[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^{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^{10} and 10^{52}, 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.
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_{1}^{a1} p_{2}^{a2} ... p_{m}^{am}, then S_{g}(n)= S_{g}(p_{1}^{a1}) S_{g}(p_{2}^{a2}) ... S_{g}(p_{m}^{am}). We can now prove various facts we used above.
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_{1}^{b1-1} ... p_{m}^{bm-1}, where a may be zero, p_{1}, ..., p_{m} are distinct odd primes, and b_{1}, ..., 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}^{bi-1})/p_{i}^{bi-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^{2}/6, so the product taken over all primes except 2 and 3 is (pi^{2}/6)/((4/3)(9/8)). Therefore, S_{modified exponential}(n)/n is no bigger than (3/2)(7/6)((pi^{2}/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.
David Moews (dmoews@fastmail.fm)
Last significant revision 30-XII-2010