Aliquot sequence

Definiton

An aliquot sequence is a sequence of numbers generated from an initial number using the sigma [math]\displaystyle{ \sigma(n) }[/math] function.

The sequence is generated using the proper divisors of the number, n, which are all the divisors of the number, excluding itself. Therefore, sequences are generated thusly:

[math]\displaystyle{ s_0 = n; }[/math]

[math]\displaystyle{ s_1 = \sigma(n) - n; }[/math]

[math]\displaystyle{ s_2 = \sigma(s_1) - s_1 }[/math]

.

.

[math]\displaystyle{ s_n = \sigma(s_{n-1}) - s_{n-1} }[/math]

So the sequence starting at 10 would be:

[math]\displaystyle{ s_0\ =\ 10,\ \sigma(10)=1\ +\ 2\ +\ 5\ +\ 10 }[/math]

[math]\displaystyle{ s_1\ =\ 18\ -\ 10\ =\ 8,\ \sigma(8)\ =\ 1\ +\ 2\ +\ 4\ +\ 8 }[/math]

[math]\displaystyle{ s_2\ =\ 15\ -\ 8\ =\ 7,\ \sigma(7)\ =\ 1\ +\ 7 }[/math]

[math]\displaystyle{ s_3\ =\ 8\ -\ 7\ =\ 1,\ \sigma(1)\ =\ 1 }[/math]

[math]\displaystyle{ s_4\ =\ 1\ -\ 1\ =\ 0 }[/math]

and therefore terminates. The sequence is usually defined as ending when the result of the previous step is a prime, so the sequence starting at 10 ends at line 2 with the prime 7.

Calculating the divisors and sigma of a number

The naive way to find the divisors of a number are to check the numbers from 1 to [math]\displaystyle{ sqrt{n} }[/math] to see if they divide the number. Easy to do if the number is, say, less than 10 digits, but very slow if the number gets into the 30+ digit range.

It turns out that if you know the prime factorization of a number, you can generate the sigma from that knowledge.

If you have a number, N, and its prime factorization is:

[math]\displaystyle{ N=p^{a}*q^{b}*r^{c} }[/math]. . .

you can calculate the following product and arrive at the sum of the divisors:

[math]\displaystyle{ Sum=\frac{p^{a+1}-1}{p-1}\ *\ \frac{q^{b+1}-1}{q-1}\ *\ \frac{r^{c+1}-1}{r-1}\ *\ }[/math] . . .

Using the current factoring tools available today, ECM, MPQS, and the GNFS as needed, sequences can be calculated into the 100s of digits.

Length of sequences and the Catalan-Dickson Conjecture

Aliquot sequences can run anywhere from 1 step (sequences starting at a prime) to thousands of lines.

Sequences starting at even numbers are, as a rule, longer than sequences starting at odd numbers. This is because the '2' appearing in factorizations of even numbers persists, and can appear at higher powers, which tends to result in abundant numbers. Also, the '2' can only disappear under specific circumstances, which are harder to achieve as the length of the numbers increase.

The Catalan-Dickson Conjecture states that all sequences are bounded, that they either terminate in a prime, a perfect number, or fall into a cycle of length 2, amicable numbers, or longer, sociable numbers, but other researchers disagree with this conjecture.

The numbers under 1000 whose sequences could be unbounded are 276, 306, 396, 552, 564, 660, 696, 780, 828, 888, 966 and 996. However, some of these sequences merge with earlier ones. For example, 396 merges with 276 because the sequence of 276 starts 276, 396... Only the lowest of the "family" of sequences is counted as a full open-end sequence, and the others are known as side-sequences. The open-end sequences under 1000 are 276, 552, 564, 660 and 966.

There are 902 open-end sequences under [math]\displaystyle{ 10^5 }[/math], and 9282 under [math]\displaystyle{ 10^6 }[/math] as of January 23 2011.

(Reference: http://www.mersenneforum.org/showpost.php?p=248644&postcount=654)

Drivers and guides

Perfect numbers

During the calculation of a sequence, several prime factorization structures can tend to persist. The most stable form of these is called a driver. This is because they tend to drive the sequence higher at every step. Of the drivers, the worst ones are the perfect numbers:

[math]\displaystyle{ 2^ \ \ *\ 3 }[/math]

[math]\displaystyle{ 2^2\ *\ 7 }[/math]

[math]\displaystyle{ 2^4\ *\ 31 }[/math]

[math]\displaystyle{ 2^6\ *\ 127 }[/math]

The other drivers

The other drivers are

[math]\displaystyle{ 2^3\ *\ 3 }[/math]

[math]\displaystyle{ 2^3\ *\ 3\ *\ 5 }[/math]

[math]\displaystyle{ 2^5\ *\ 3\ *\ 7 }[/math]

[math]\displaystyle{ 2^9\ *\ 3\ *\ 11\ *\ 31 }[/math]

The last of these has only been seen a couple of times 'in the wild'.

The downdriver

A special form of driver is '2', not raised to a power and unaccompanied by '3'. This form of driver is termed the downdriver because when a line factors with this driver, the sequence can decrease in size. Depending on the size of the other prime(s) in the factorization, a sequence can decrease by close to 50% for each line when driven by the downdriver. Unfortunately, the downdriver is less stable than all of the other drivers except [math]\displaystyle{ 2^3\ *\ 3 }[/math] and will be lost on the next line if a number factors as

[math]\displaystyle{ 2\ *\ p }[/math], where p is of the form [math]\displaystyle{ 4n+1 }[/math]

Guides

Guides are less persistent than drivers, but can also tend to appear in subsequent lines of a sequence. Some examples of guides are:

[math]\displaystyle{ 2^2 }[/math]

[math]\displaystyle{ 2^3 }[/math]

[math]\displaystyle{ 2^3\ *\ 5 }[/math]

[math]\displaystyle{ 2^5\ *\ 3 }[/math]\

(For a more complete analysis of drivers and the conditions needed to escape a driver, see Clifford Stern's analysis page.)

External links

• Wolfgang Creyaufmuller's site Website devoted to extending open-ended sequences up to 100 digits.
• Aliquot sequences from the trenches Updated more often than Wolfgang's site, there is also a page with a detailed analysis of the mathematics behind guide/driver evolution.
• Aliquot sequence
• Mersenneforum section on aliquot sequences. Check this thread for current sequence status.