Do all aliquot sequences eventually end with a prime number, a perfect number, or a set of amicable or sociable numbers? (Catalan's aliquot sequence conjecture)
In mathematics, an aliquot sequence is a sequence of positive integers in which each term is the sum of the proper divisors of the previous term. If the sequence reaches the number 1, it ends, since the sum of the proper divisors of 1 is 0.
The aliquot sequence starting with a positive integer k can be defined formally in terms of the sum-of-divisors function σ_{1} or the aliquot sum function s in the following way:^{[1]}
and s(0) is undefined.
For example, the aliquot sequence of 10 is 10, 8, 7, 1, 0 because:
Many aliquot sequences terminate at zero; all such sequences necessarily end with a prime number followed by 1 (since the only proper divisor of a prime is 1), followed by 0 (since 1 has no proper divisors). See (sequence A080907 in the OEIS) for a list of such numbers up to 75. There are a variety of ways in which an aliquot sequence might not terminate:
n | Aliquot sequence of n | length (OEIS: A098007) | n | Aliquot sequence of n | length (OEIS: A098007) | n | Aliquot sequence of n | length (OEIS: A098007) | n | Aliquot sequence of n | length (OEIS: A098007) |
0 | 0 | 1 | 12 | 12, 16, 15, 9, 4, 3, 1, 0 | 8 | 24 | 24, 36, 55, 17, 1, 0 | 6 | 36 | 36, 55, 17, 1, 0 | 5 |
1 | 1, 0 | 2 | 13 | 13, 1, 0 | 3 | 25 | 25, 6 | 2 | 37 | 37, 1, 0 | 3 |
2 | 2, 1, 0 | 3 | 14 | 14, 10, 8, 7, 1, 0 | 6 | 26 | 26, 16, 15, 9, 4, 3, 1, 0 | 8 | 38 | 38, 22, 14, 10, 8, 7, 1, 0 | 8 |
3 | 3, 1, 0 | 3 | 15 | 15, 9, 4, 3, 1, 0 | 6 | 27 | 27, 13, 1, 0 | 4 | 39 | 39, 17, 1, 0 | 4 |
4 | 4, 3, 1, 0 | 4 | 16 | 16, 15, 9, 4, 3, 1, 0 | 7 | 28 | 28 | 1 | 40 | 40, 50, 43, 1, 0 | 5 |
5 | 5, 1, 0 | 3 | 17 | 17, 1, 0 | 3 | 29 | 29, 1, 0 | 3 | 41 | 41, 1, 0 | 3 |
6 | 6 | 1 | 18 | 18, 21, 11, 1, 0 | 5 | 30 | 30, 42, 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1, 0 | 16 | 42 | 42, 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1, 0 | 15 |
7 | 7, 1, 0 | 3 | 19 | 19, 1, 0 | 3 | 31 | 31, 1, 0 | 3 | 43 | 43, 1, 0 | 3 |
8 | 8, 7, 1, 0 | 4 | 20 | 20, 22, 14, 10, 8, 7, 1, 0 | 8 | 32 | 32, 31, 1, 0 | 4 | 44 | 44, 40, 50, 43, 1, 0 | 6 |
9 | 9, 4, 3, 1, 0 | 5 | 21 | 21, 11, 1, 0 | 4 | 33 | 33, 15, 9, 4, 3, 1, 0 | 7 | 45 | 45, 33, 15, 9, 4, 3, 1, 0 | 8 |
10 | 10, 8, 7, 1, 0 | 5 | 22 | 22, 14, 10, 8, 7, 1, 0 | 7 | 34 | 34, 20, 22, 14, 10, 8, 7, 1, 0 | 9 | 46 | 46, 26, 16, 15, 9, 4, 3, 1, 0 | 9 |
11 | 11, 1, 0 | 3 | 23 | 23, 1, 0 | 3 | 35 | 35, 13, 1, 0 | 4 | 47 | 47, 1, 0 | 3 |
The lengths of the aliquot sequences that start at n are
The final terms (excluding 1) of the aliquot sequences that start at n are
Numbers whose aliquot sequence terminates in 1 are
Numbers whose aliquot sequence known to terminate in a perfect number, other than perfect numbers themselves (6, 28, 496, ...), are
Numbers whose aliquot sequence terminates in a cycle with length at least 2 are
Numbers whose aliquot sequence is not known to be finite or eventually periodic are
A number that is never the successor in an aliquot sequence is called an untouchable number.
An important conjecture due to Catalan, sometimes called the Catalan–Dickson conjecture, is that every aliquot sequence ends in one of the above ways: with a prime number, a perfect number, or a set of amicable or sociable numbers.^{[3]} The alternative would be that a number exists whose aliquot sequence is infinite yet never repeats. Any one of the many numbers whose aliquot sequences have not been fully determined might be such a number. The first five candidate numbers are often called the Lehmer five (named after D.H. Lehmer): 276, 552, 564, 660, and 966.^{[4]} However, it is worth noting that 276 may reach a high apex in its aliquot sequence and then descend; the number 138 reaches a peak of 179931895322 before returning to 1.
Guy and Selfridge believe the Catalan–Dickson conjecture is false (so they conjecture some aliquot sequences are unbounded above (i.e., diverge)).^{[5]}
As of April 2015^{[update]}, there were 898 positive integers less than 100,000 whose aliquot sequences have not been fully determined, and 9190 such integers less than 1,000,000.^{[6]}
The aliquot sequence can be represented as a directed graph, , for a given integer , where denotes the sum of the proper divisors of .^{[7]} Cycles in represent sociable numbers within the interval . Two special cases are loops that represent perfect numbers and cycles of length two that represent amicable pairs.