An Introduction to Aliquot Sequences
An Introduction to Aliquot Sequences
By:WilliamMunizzi
Introduction
An aliquot sequence is a sequence of numbers where each successive term is the sum of all proper divisors (all divisors not including the number itself) of the previous term. For example, beginning with the term =10 generates the following sequence
a
0
a
0
a
1
a
2
a
3
a
4
The sequence terminates at 0, which has no proper divisors. The number 10 is considered a “deficient” number, since its Aliquot sequence descends monotonically to 0. Conversely, consider the sequence beginning at =18
a
0
a
0
a
1
a
2
a
3
a
4
While beginning with =18 yielded the same number of sequence terms as =10, we observe that the elements of the sequence increase in value momentarily before descending back to 0. In this context, the number 18 is considered an “abundant” number.
All Aliquot sequences need not ultimately terminate with 0, however. Consider the case for=6, which repeats
a
0
a
0
All Aliquot sequences need not ultimately terminate with 0, however. Consider the case for
a
0
a
0
a
1
a
2
a
3
a
4
never terminating with a 0. This phenomena occurs since 6 is a “perfect number”, meaning the number itself equals the sum of its proper divisors. The number 6 is the smallest perfect number, but others include 28, 496, 8128 ... and so on. Therefore, an Aliquot sequence may likewise terminate if a perfect number is reached at any point in the sequence. Intriguingly certain numbers, while not perfect themselves, admit an Aliquot sequence that terminates at a perfect number. Consider, for example, the case when =119
a
0
a
0
a
1
a
2
a
3
a
4
Non-perfect numbers with Aliquot sequences that terminate on perfect number are known as “aspiring” numbers. Other examples of aspiring numbers include 25, 95, 143, and so forth.
Aliquot sequences can likewise end up in a non-terminating pair of numbers, where the proper divisors of one number sum to the other number, and vice-versa. Consider the case for=220, with an Aliquot sequence
Aliquot sequences can likewise end up in a non-terminating pair of numbers, where the proper divisors of one number sum to the other number, and vice-versa. Consider the case for
a
0
a
0
a
1
a
2
a
3
a
4
Accordingly, the numbers 220 and 284 are known as an “amicable pair”. The set {220, 284} is the smallest such amicable pair, but others include {1184, 1210}, {2620, 2924}, and more. The sets of perfect numbers and amicable numbers are subsets of a larger class, known as “sociable” numbers. Sociable numbers are defined as those numbers with a periodic Aliquot sequence. The number 1547860 is a sociable number, with an associated Aliquot sequence
A[1547860] = , 1727636, 1305184, 1264460, 1547860, ...}
{1547860
While simple in their construction, Aliquot sequences reveal interesting features about the relationship between integers. They have even been linked to several unsolved problems in mathematics. Perhaps most famous is the Catalan-Dickson conjecture which states that every Aliquot sequence must end in either the number 0, or a sociable number (perfect, amicable, or otherwise). A proof of the Catalan-Dickson conjecture has remained elusive to date, with many believing the statement to be false. Those opposed to the statement, as written, believe certain numbers admit Aliquot sequences with elements unbounded in the positive integers.
Perhaps most intriguing is the demonstration of numbers whose Aliquot sequences have to be determined, even after an enormous number of terms have been computed. In fact, among the positive integers from 1 to 1000 we have identified 5 numbers with undetermined Aliquot sequences. These numbers: 276, 552, 564, 660, and 966 are known as the “Lehmer Five” after their discoverer Derrick Lehmer. Aliquot sequences associated with the Lehmer five have not yet been observed to terminate, despite the allied assistance of advanced computing power.
Perhaps most intriguing is the demonstration of numbers whose Aliquot sequences have to be determined, even after an enormous number of terms have been computed. In fact, among the positive integers from 1 to 1000 we have identified 5 numbers with undetermined Aliquot sequences. These numbers: 276, 552, 564, 660, and 966 are known as the “Lehmer Five” after their discoverer Derrick Lehmer. Aliquot sequences associated with the Lehmer five have not yet been observed to terminate, despite the allied assistance of advanced computing power.
Function Definitions (Run this Section)
In this section we define a simple function for computing the Aliquot sequence of a given initial positive integer.
(*Functiontoperformthesumofproperdivisors.*)AliquotProcess[num_]:=Total[Delete[Divisors[num],-1]];(*FunctiontoiterateAliquotProcess[num_],givenanintialinputnumber,untilthesequenceterminates.*)AliquotSequence[initial_]:=Block[{seq={},lastTerm=0,nextTerm=initial},While[And[MemberQ[seq,nextTerm]==False,nextTerm!=1],lastTerm=nextTerm;AppendTo[seq,lastTerm];nextTerm=AliquotProcess[lastTerm]];AppendTo[seq,nextTerm]]
Examples and Plots
Preliminary Examples
Preliminary Examples
Below we include some simple cases of Aliquot sequences for various positive integers, to demonstrate functionality.
In[]:=
AliquotSequence[10]
Out[]=
{10,8,7,1}
In[]:=
AliquotSequence[16]
Out[]=
{16,15,9,4,3,1}
In[]:=
AliquotSequence[35]
Out[]=
{35,13,1}
We could likewise generate the set of Aliquot sequences for a range of numbers, e.g. the positive integers from 1--15
In[]:=
Table[Print[AliquotSequence[i]],{i,15}];
{1}
{2,1}
{3,1}
{4,3,1}
{5,1}
{6,6}
{7,1}
{8,7,1}
{9,4,3,1}
{10,8,7,1}
{11,1}
{12,16,15,9,4,3,1}
{13,1}
{14,10,8,7,1}
{15,9,4,3,1}
Plotting the above sequences enables an intuitive look into the behavior for each.
In[]:=
ListLinePlot[Table[AliquotSequence[i],{i,1,15}],PlotRange->All]
Out[]=
Performing this process for powers of 2 we see that, despite the relatively large integers being inputted (up to 1267650600228229401496703205376), all sequences plotted terminate in a short number of steps.
In[]:=
powersOf2=Table[AliquotSequence[2^i],{i,2,100}];ListLinePlot[Log/@powersOf2]
Out[]=
More Interesting Examples
More Interesting Examples
As we extend to larger and larger integers, the surprising behavior of certain Aliquot sequences is revealed. Consider, for example, the number 138 and it’s associated sequence. In 178 steps, the Aliquot sequence of 138 reaches values as large as 179931895322 before ultimately decaying to 0 and terminating. Such seemingly unpredictable behavior is precisely what makes a general proof of the Catalan-Dickson conjecture difficult, as well as what underlies the intriguing nature of Aliquot sequences.
In[]:=
aSequence138=AliquotSequence[138];ListLinePlot[aSequence138]Length[aSequence138]Max[aSequence138]
Out[]=
To better visualize the evolution of sequences with large values, we could instead plot the Aliquot sequence on a Logarithmic scale. Here, the exponential growth and decay between successive terms is readily displayed in a pleasant “mountainous” vista.
If we plot the Aliquot sequences of all positive integers up to the first Lehmer Five number, 276, we observe that several integers exhibit identical sequence behavior to 138.
Prime Numbers
Prime Numbers
In the context of Aliquot sequences, prime numbers may admit the least interesting sequences. By definition a prime number P only admits divisors 1 and P, and therefore it’s Aliquot sequence reaches 1 after only a single iteration. Nevertheless, plotting all Aliquot sequences of primes in a given range can yield a satisfying display. For example, let us plot the Aliquot sequences for the first 50 prime numbers.
Similarly for the first 500 primes.
Fibonacci Numbers
Fibonacci Numbers
A similarly-structured sequence, the Fibonacci sequence, defines each subsequent term according to the sum of all preceding terms. Computing the Aliquot sequence for the first 25 Fibonacci numbers, we find the following.
As it turns out, the 24th Fibonacci number (46368) admits a rather long Aliquot sequence of 218 elements.
Catalan Numbers
Catalan Numbers
An interesting set of numbers that, while many of its elements abundant, does not yield Aliquot sequences of substantial magnitude nor length are the Catalan numbers.
Zeta Zeroes
Zeta Zeroes
We could continue playing around with integers, plotting the Aliquot sequence for the nearest (imaginary) integer to Riemann Zeta function zeroes. For the nearest integers to the first 46 zeroes, we have the following.
Coincidentally, the imaginary part of the 47th Zeta function zero is closest in whole number value to 138.