Editing Aliquot sequence

{{short description|Mathematical recursive sequence}}
{{pp-sock|small=yes}}
{{unsolved|mathematics|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 divisor]]s of the previous term. If the sequence reaches the number 1, it ends, since the sum of the proper divisors of 1 is 0.

==Definition and overview==
The [[wiktionary:aliquot|aliquot]] sequence starting with a positive integer {{mvar|k}} can be defined formally in terms of the [[divisor function|sum-of-divisors function]] {{math|''σ''<sub>1</sub>}} or the [[aliquot sum]] function {{mvar|s}} in the following way:<ref name="mw">{{MathWorld | urlname=AliquotSequence | title=Aliquot Sequence}}</ref>
<math display=block>\begin{align}
s_0 &= k \\[4pt]
s_n &= s(s_{n-1}) = \sigma_1(s_{n-1}) - s_{n-1} \quad \text{if} \quad s_{n-1} > 0 \\[4pt]
s_n &= 0 \quad \text{if} \quad s_{n-1} = 0 \\[4pt]
s(0) &= \text{undefined}
\end{align}</math>
If the {{math|1=''s''{{sub|''n''-1}} = 0}} condition is added, then the terms after 0 are all 0, and all aliquot sequences would be infinite, and we can conjecture that all aliquot sequences are [[limit (mathematics)|convergent]], the limit of these sequences are usually 0 or 6.

For example, the aliquot sequence of 10 is {{nowrap|10, 8, 7, 1, 0}} because:

<math display=block>\begin{align}
\sigma_1(10) -10 &= 5 + 2 + 1 = 8, \\[4pt]
\sigma_1(8) - 8 &= 4 + 2 + 1 = 7, \\[4pt]
\sigma_1(7) - 7 &= 1, \\[4pt]
\sigma_1(1) - 1 &= 0. 
\end{align}</math>

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 {{OEIS|id=A080907}} for a list of such numbers up to 75. There are a variety of ways in which an aliquot sequence might not terminate:
* A [[perfect number]] has a repeating aliquot sequence of period 1. The aliquot sequence of 6, for example, is {{nowrap|6, 6, 6, 6, ...}}
* An [[amicable number]] has a repeating aliquot sequence of period 2. For instance, the aliquot sequence of 220 is {{nowrap|220, 284, 220, 284, ...}}
* A [[sociable number]] has a repeating aliquot sequence of period 3 or greater. (Sometimes the term ''sociable number'' is used to encompass amicable numbers as well.) For instance, the aliquot sequence of 1264460 is {{nowrap|1264460, 1547860, 1727636, 1305184, 1264460, ...}}
* Some numbers have an aliquot sequence which is eventually periodic, but the number itself is not perfect, amicable, or sociable. For instance, the aliquot sequence of 95 is {{nowrap|95, 25, 6, 6, 6, 6, ...}} Numbers like 95 that are not perfect, but have an eventually repeating aliquot sequence of period 1 are called '''aspiring numbers'''.<ref>{{Cite OEIS|1=A063769|2=Aspiring numbers: numbers whose aliquot sequence terminates in a perfect number. }}</ref>

{| class="wikitable mw-collapsible mw-collapsed"
|+ class="nowrap" | Aliquot sequences from 0 to 47
|-
! {{mvar|n}} !! Aliquot sequence of {{mvar|n}} !! Length ({{oeis|A098007}})
|-
! 0
| 0 || 1
|-
! 1
| 1, 0 || 2
|-
! 2
| 2, 1, 0 || 3
|-
! 3
| 3, 1, 0 || 3
|-
! 4
| 4, 3, 1, 0 || 4
|-
! 5
| 5, 1, 0 || 3
|-
! 6
| 6 || 1
|-
! 7
| 7, 1, 0 || 3
|-
! 8
| 8, 7, 1, 0 || 4
|-
! 9
| 9, 4, 3, 1, 0 || 5
|-
! 10
| 10, 8, 7, 1, 0 || 5
|-
! 11
| 11, 1, 0 || 3
|-
! 12
| 12, 16, 15, 9, 4, 3, 1, 0 || 8
|-
! 13
| 13, 1, 0 || 3
|-
! 14
| 14, 10, 8, 7, 1, 0 || 6
|-
! 15
| 15, 9, 4, 3, 1, 0 || 6
|-
! 16
| 16, 15, 9, 4, 3, 1, 0 || 7
|-
! 17
| 17, 1, 0 || 3
|-
! 18
| 18, 21, 11, 1, 0 || 5
|-
! 19
| 19, 1, 0 || 3
|-
! 20
| 20, 22, 14, 10, 8, 7, 1, 0 || 8
|-
! 21
| 21, 11, 1, 0 || 4
|-
! 22
| 22, 14, 10, 8, 7, 1, 0 || 7
|-
! 23
| 23, 1, 0 || 3
|-
! 24
| 24, 36, 55, 17, 1, 0 || 6
|-
! 25
| 25, 6 || 2
|-
! 26
| 26, 16, 15, 9, 4, 3, 1, 0 || 8
|-
! 27
| 27, 13, 1, 0 || 4
|-
! 28
| 28 || 1
|-
! 29
| 29, 1, 0 || 3
|-
! 30
| 30, 42, 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1, 0 || 16
|-
! 31
| 31, 1, 0 || 3
|-
! 32
| 32, 31, 1, 0 || 4
|-
! 33
| 33, 15, 9, 4, 3, 1, 0 || 7
|-
! 34
| 34, 20, 22, 14, 10, 8, 7, 1, 0 || 9
|-
! 35
| 35, 13, 1, 0 || 4
|-
! 36
| 36, 55, 17, 1, 0 || 5
|-
! 37
| 37, 1, 0 || 3
|-
! 38
| 38, 22, 14, 10, 8, 7, 1, 0 || 8
|-
! 39
| 39, 17, 1, 0 || 4
|-
! 40
| 40, 50, 43, 1, 0 || 5
|-
! 41
| 41, 1, 0 || 3
|-
! 42
| 42, 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1, 0 || 15
|-
! 43
| 43, 1, 0 || 3
|-
! 44
| 44, 40, 50, 43, 1, 0 || 6
|-
! 45
| 45, 33, 15, 9, 4, 3, 1, 0 || 8
|-
! 46
| 46, 26, 16, 15, 9, 4, 3, 1, 0 || 9
|-
! 47
| 47, 1, 0 || 3
|}

The lengths of the aliquot sequences that start at {{mvar|n}} are
:1, 2, 2, 3, 2, 1, 2, 3, 4, 4, 2, 7, 2, 5, 5, 6, 2, 4, 2, 7, 3, 6, 2, 5, 1, 7, 3, 1, 2, 15, 2, 3, 6, 8, 3, 4, 2, 7, 3, 4, 2, 14, 2, 5, 7, 8, 2, 6, 4, 3, ... {{OEIS|id=A044050}}

The final terms (excluding 1) of the aliquot sequences that start at {{mvar|n}} are
:1, 2, 3, 3, 5, 6, 7, 7, 3, 7, 11, 3, 13, 7, 3, 3, 17, 11, 19, 7, 11, 7, 23, 17, 6, 3, 13, 28, 29, 3, 31, 31, 3, 7, 13, 17, 37, 7, 17, 43, 41, 3, 43, 43, 3, 3, 47, 41, 7, 43, ... {{OEIS|id=A115350}}

Numbers whose aliquot sequence terminates in 1 are
:1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, ... {{OEIS|id=A080907}}

Numbers whose aliquot sequence known to terminate in a [[perfect number]], other than perfect numbers themselves (6, 28, 496, ...), are 
:25, 95, 119, 143, 417, 445, 565, 608, 650, 652, 675, 685, 783, 790, 909, 913, ... {{OEIS|id=A063769}}

Numbers whose aliquot sequence terminates in a cycle with length at least 2 are
:220, 284, 562, 1064, 1184, 1188, 1210, 1308, 1336, 1380, 1420, 1490, 1604, 1690, 1692, 1772, 1816, 1898, 2008, 2122, 2152, 2172, 2362, ... {{OEIS|id=A121507}}

Numbers whose aliquot sequence is not known to be finite or eventually periodic are
:276, 306, 396, 552, 564, 660, 696, 780, 828, 888, 966, 996, 1074, 1086, 1098, 1104, 1134, 1218, 1302, 1314, 1320, 1338, 1350, 1356, 1392, 1398, 1410, 1464, 1476, 1488, ... {{OEIS|id=A131884}}

A number that is never the successor in an aliquot sequence is called an [[untouchable number]].
:[[2 (number)|2]], [[5 (number)|5]], [[52 (number)|52]], [[88 (number)|88]], [[96 (number)|96]], [[120 (number)|120]], [[124 (number)|124]], [[146 (number)|146]], [[162 (number)|162]], [[188 (number)|188]], [[206 (number)|206]], [[210 (number)|210]], [[216 (number)|216]], [[238 (number)|238]], [[246 (number)|246]], [[248 (number)|248]], 262, 268, [[276 (number)|276]], [[288 (number)|288]], [[290 (number)|290]], 292, 304, 306, 322, 324, 326, 336, 342, 372, 406, 408, 426, 430, 448, 472, 474, 498, ... {{OEIS|id=A005114}}

== Catalan–Dickson conjecture ==
An important [[conjecture]] due to [[Eugène Charles Catalan|Catalan]], sometimes called the Catalan–[[Leonard Eugene Dickson|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.<ref>{{MathWorld | urlname=CatalansAliquotSequenceConjecture | title=Catalan's Aliquot Sequence Conjecture}}</ref> 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 [[Derrick Henry Lehmer|D.H. Lehmer]]): [[276 (number)|276]], 552, 564, 660, and 966.<ref>{{cite web|url=http://www.aliquot.de/lehmer.htm|title=Lehmer Five|first=Wolfgang|last=Creyaufmüller|date=May 24, 2014|access-date=June 14, 2015}}</ref> However, 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.

[[Richard K. Guy|Guy]] and [[John Selfridge|Selfridge]] believe the Catalan–Dickson conjecture is false (so they conjecture some aliquot sequences are [[bounded function|unbounded]] above (i.e., diverge)).<ref>A. S. Mosunov, [http://www.cs.uleth.ca/~hadi/2016-09-29-aliquot_sequences.pdf What do we know about aliquot sequences?]</ref>

== Systematically searching for aliquot sequences ==

The aliquot sequence can be represented as a [[directed graph]], <math>G_{n,s}</math>, for a given integer <math>n</math>, where <math>s(k)</math> denotes the sum of the proper divisors of <math>k</math>.<ref>{{citation|title=Distributed cycle detection in large-scale sparse graphs|first1=Rodrigo Caetano|last1=Rocha|first2=Bhalchandra|last2=Thatte|year=2015|publisher=Simpósio Brasileiro de Pesquisa Operacional (SBPO)|doi=10.13140/RG.2.1.1233.8640}}</ref> [[cycle (graph theory)|Cycles]] in <math>G_{n,s}</math> represent sociable numbers within the interval <math>[1,n]</math>. Two special cases are loops that represent [[perfect numbers]] and cycles of length two that represent [[amicable pairs]].

== See also ==
* [[Arithmetic dynamics]]

== Notes ==
{{reflist}}

== References ==
{{refbegin}}
* Manuel Benito; Wolfgang Creyaufmüller; Juan Luis Varona; Paul Zimmermann. [https://web.archive.org/web/20041015194432/http://www.expmath.org/expmath/volumes/11/11.2/3630finishes1.pdf ''Aliquot Sequence 3630 Ends After Reaching 100 Digits'']. Experimental Mathematics, vol. 11, num. 2, Natick, MA, 2002, p.&nbsp;201–206.
* W. Creyaufmüller. ''Primzahlfamilien - Das Catalan'sche Problem und die Familien der Primzahlen im Bereich 1 bis 3000 im Detail''. Stuttgart 2000 (3rd ed.), 327p.
{{refend}}

==External links==
*[http://www.rechenkraft.net/aliquot/AllSeq.html Current status of aliquot sequences with start term below 4 million]
*[https://web.archive.org/web/20140502102524/http://amicable.homepage.dk/tables.htm Tables of Aliquot Cycles] (J.O.M. Pedersen)
*[http://www.aliquot.de/aliquote.htm Aliquot Page] (Wolfgang Creyaufmüller)
*[http://christophe.clavier.free.fr/Aliquot/site/Aliquot.html Aliquot sequences] (Christophe Clavier)
*[http://www.mersenneforum.org/forumdisplay.php?f=90 Forum on calculating aliquot sequences] (MersenneForum)
*[http://www.rieselprime.de/Others/Aliquot000.htm Aliquot sequence summary page for sequences up to 100000 (there are similar pages for higher ranges)] (Karsten Bonath)
*[http://www.aliquotes.com Active research site on aliquot sequences] (Jean-Luc Garambois) {{in lang|fr}}

{{Divisor classes}}

{{DEFAULTSORT:Aliquot Sequence}}

[[Category:Arithmetic functions]]
[[Category:Divisor function]]
[[Category:Arithmetic dynamics]]