Aliquot sequences

This article page is a stub, please help by expanding it.

An aliquot sequence (or aliquot trajectory) is a recurrence in which each term is the sum of proper divisors of the previous term, where the initial term must be a positive integer, i.e.

     

a 0  =  k, k ∈ ℕ +; an  =  s1(an  − 1 ), n ≥ 1.

In the above,

s1(an  )   :=   σ1(an  )  −  an

is the sum of aliquot divisors function,

σ1(an  )

being the sum of divisors function. An aliquot sequence (other than the trivial

{1, 0}

) either

• eventually hits a prime number, which begets 1, and then the empty sum, i.e. 0 (and thus terminates, since the sum of proper divisors is defined for positive integers) (A080907);
• never hits a prime number (and thus never terminates), where it either
  • cycles, with finite order
    • 1: perfect numbers (e.g.
      {6, 6, ...}
      ) (A000396);
    • 2: amicable pairs (e.g.
      {220, 284, 220, ...}
      ) (A063990);
    • > 2: sociable numbers (e.g.
      {1264460, 1547860, 1727636, 1305184, 1264460, ...}
      ) (A003416 Sociable numbers: smallest member of each cycle.);
  • eventually cycles (by hitting a number belonging to a cycle), with finite order
    • 1: aspiring numbers (e.g.
      {25, 6, 6, ...}
      ) (A063769);
    • 2: (A??????);
    • > 2: (A??????);
  • never cycles, and is thus an infinite sequence of distinct composite terms, hence an unbounded sequence (this seems very unlikely, although the non-existence of such sequences has not yet been proved!).

An infinite unbounded aliquot sequence, growing monotonically or not, must manage to never hit any aliquot cycle whatsoever (no [even] or [odd?] perfect number, no member of an amicable pair, no member of social cycle) and it must never hit a prime number! This seems very unlikely: a term is obtained by “adding” the proper divisors of the previous term, so one would expect that hitting either a cycle or a prime number is a matter of probability (which is nonzero for each term), which would imply that a hit is eventually unavoidable (but there might be such sequences with any finite number of terms, although with decreasing probability as the number of terms increases... which corresponds to the [not yet established] truth of the Catalan–Dickson conjecture).

Table of aliquot sequences
Length = “Head length” + “tail length”, where “Head” is aliquot subsequence before reaching

m < n

and “tail” (italicized) is aliquot subsequence whence reaching

m < n

.

n Aliquot sequence of n Length L (n) A098007 0 0 1 1 1, 0 2 = 1 + L (0) 2 2, 1, 0 3 = 1 + L (1) 3 3, 1, 0 3 = 1 + L (1) 4 4, 3, 1, 0 4 = 1 + L (3) 5 5, 1, 0 3 = 1 + L (1) 6 6 1 7 7, 1, 0 3 = 1 + L (1) 8 8, 7, 1, 0 4 = 1 + L (7) 9 9, 4, 3, 1, 0 5 = 1 + L (4) 10 10, 8, 7, 1, 0 5 = 1 + L (8) 11 11, 1, 0 3 = 1 + L (1) 12 12, 16, 15, 9, 4, 3, 1, 0 8 = 3 + L (9) 13 13, 1, 0 3 = 1 + L (1) 14 14, 10, 8, 7, 1, 0 6 = 1 + L (10) 15 15, 9, 4, 3, 1, 0 6 = 1 + L (9)

n Aliquot sequence of n Length L (n) A098007 16 16, 15, 9, 4, 3, 1, 0 7 = 1 + L (15) 17 17, 1, 0 3 = 1 + L (1) 18 18, 21, 11, 1, 0 5 = 2 + L (11) 19 19, 1, 0 3 = 1 + L (1) 20 20, 22, 14, 10, 8, 7, 1, 0 8 = 2 + L (14) 21 21, 11, 1, 0 4 = 1 + L (11) 22 22, 14, 10, 8, 7, 1, 0 7 = 1 + L (14) 23 23, 1, 0 3 = 1 + L (1) 24 24, 36, 55, 17, 1, 0 6 = 3 + L (17) 25 25, 6 2 = 1 + L (6) 26 26, 16, 15, 9, 4, 3, 1, 0 8 = 1 + L (16) 27 27, 13, 1, 0 4 = 1 + L (13) 28 28 1 29 29, 1, 0 3 = 1 + L (1) 30 30, 42, 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1, 0 16 = 10 + L (15) 31 31, 1, 0 3 = 1 + L (1)

n Aliquot sequence of n Length L (n) A098007 32 32, 31, 1, 0 4 = 1 + L (31) 33 33, 15, 9, 4, 3, 1, 0 7 = 1 + L (15) 34 34, 20, 22, 14, 10, 8, 7, 1, 0 9 = 1 + L (20) 35 35, 13, 1, 0 4 = 1 + L (13) 36 36, 55, 17, 1, 0 5 = 2 + L (17) 37 37, 1, 0 3 = 1 + L (1) 38 38, 22, 14, 10, 8, 7, 1, 0 8 = 1 + L (22) 39 39, 17, 1, 0 4 = 1 + L (17) 40 40, 50, 43, 1, 0 5 = 3 + L (1) 41 41, 1, 0 3 = 1 + L (1) 42 42, 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1, 0 15 = 8 + L (33) 43 43, 1, 0 3 = 1 + L (1) 44 44, 40, 50, 43, 1, 0 6 = 1 + L (40) 45 45, 33, 15, 9, 4, 3, 1, 0 8 = 1 + L (33) 46 46, 26, 16, 15, 9, 4, 3, 1, 0 9 = 1 + L (26) 47 47, 1, 0 3 = 1 + L (1)

n Aliquot sequence of n Length L (n) A098007 48 48, 76, 64, 63, 41, 1, 0 7 = 4 + L (41) 49 49, 8, 7, 1, 0 5 = 1 + L (8) 50 50, 43, 1, 0 4 = 1 + L (43) 51 51, 21, 11, 1, 0 5 = 1 + L (21) 52 52, 46, 26, 16, 15, 9, 4, 3, 1, 0 10 = 1 + L (46) 53 53, 1, 0 3 = 1 + L (1) 54 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1, 0 14 = 6 + L (45) 55 55, 17, 1, 0 4 = 1 + L (17) 56 56, 64, 63, 41, 1, 0 6 = 3 + L (41) 57 57, 23, 1, 0 4 = 1 + L (23) 58 58, 32, 31, 1, 0 5 = 1 + L (32) 59 59, 1, 0 3 = 1 + L (1) 60 60, 108, 172, 136, 134, 70, 74, 40, 50, 43, 1, 0 12 = 7 + L (40) 61 61, 1, 0 3 = 1 + L (1) 62 62, 34, 20, 22, 14, 10, 8, 7, 1, 0 10 = 1 + L (34) 63 63, 41, 1, 0 4 = 1 + L (41)

Catalan’s aliquot sequence conjecture

In 1888, Eugène Charles Catalan proposed the [not yet established and probably false] conjecture

Conjecture (Catalan’s aliquot sequence conjecture, 1888). (Eugene Catalan)

Every sequence contains “either unity or a perfect number.”

The conjecture was amended by Leonard Eugene Dickson

Conjecture (Catalan–Dickson conjecture). (Leonard Eugene Dickson)

No unbounded aliquot sequences exist (“every non-periodic chain contains a prime”).*

* Which means that every aliquot sequence either terminates in a prime number followed by 1, is an aliquot cycle (a perfect number, a friendly pair or an aliquot cycle of sociable numbers) or eventually reaches an aliquot cycle.

Paul Erdős and Hendrik Lenstra postulated that unbounded aliquot sequences do exist.

Lehmer five

The Lehmer five (named after Derrick Henry Lehmer), 276, 552, 564, 660 and 966 may potentially have an unbounded aliquot sequence (while they may also lead to aliquot sequence terms so large that their prime factorization becomes intractable, while a ridiculously large prime number or some member of an aliquot cycle (e.g. a ridiculously large perfect number, amicable number or sociable number), lies on the trajectory, after a ridiculously large number of iterations...).

Sequences

A098007 Length of aliquot sequence for

n

, or −1 if aliquot sequence never cycles.

{2, 3, 3, 4, 3, 1, 3, 4, 5, 5, 3, 8, 3, 6, 6, 7, 3, 5, 3, 8, 4, 7, 3, 6, 2, 8, 4, 1, 3, 16, 3, 4, 7, 9, 4, 5, 3, 8, 4, 5, 3, 15, 3, 6, 8, 9, 3, 7, 5, 4, 5, 10, 3, 14, 4, 6, 4, 5, 3, 12, 3, 10, 4, 5, 4, 13, 3, 6, 5, 7, 3, 10, 3, 6, ...}

A098008 Length of transient part of aliquot sequence for

n

, or −1 if transient part is infinite. (A [finite] transient part precedes a cyclic part.)

{1, 2, 2, 3, 2, 0, 2, 3, 4, 4, 2, 7, 2, 5, 5, 6, 2, 4, 2, 7, 3, 6, 2, 5, 1, 7, 3, 0, 2, 15, 2, 3, 6, 8, 3, 4, 2, 7, 3, 4, 2, 14, 2, 5, 7, 8, 2, 6, 4, 3, 4, 9, 2, 13, 3, 5, 3, 4, 2, 11, 2, 9, 3, 4, 3, 12, 2, 5, 4, 6, 2, 9, 2, 5, 5, 5, ...}

A080907 Numbers whose aliquot sequence terminates in a 1. ({1} ∪ {primes} ∪ {A127162})

{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, 51, ...}

A127162 Composite numbers whose aliquot sequences terminate by encountering a prime number.

{4, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, ...}

A126016 Numbers whose aliquot sequence does not terminate in 1. (Necessarily composite numbers.)

{6, 25, 28, 95, 119, 143, 220, ...}

&

{276?, 284, 306?, 396?, 417, 445, 496, ...}

A115350 Termination of the aliquot sequence starting at

n

. (For

n  > 1

: shows either a prime number or the first perfect number [Catalan]; shows either a prime number or the first member of an aliquot cycle [Dickson].)

{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, 11, 3, ...}

A000396 Perfect numbers

n

:

n

is equal to the sum of the proper divisors of

n

.

{6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, ...}

A063769 Aspiring numbers: numbers whose aliquot sequence terminates in a perfect number.

{25, 95, 119, 143, 417, 445, 565, 608, 650, 652, 675, 685, 783, 790, 909, 913, ...}

A063990 Amicable numbers.

{220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368, 10744, 10856, 12285, 14595, 17296, 18416, 63020, 66928, 66992, 67095, 69615, 71145, 76084, 79750, 87633, 88730, 100485, ...}

A?????? Numbers whose aliquot sequence terminates in an aliquot cycle of amicable numbers.

{?, ...}

A003416 Sociable numbers: smallest member of each cycle.

{12496, 14316, 1264460, 2115324, 2784580, 4938136, 7169104, 18048976, 18656380, 28158165, 46722700, 81128632, 174277820, 209524210, 330003580, 498215416, 805984760, 1095447416, ...}

A?????? Numbers whose aliquot sequence terminates in an aliquot cycle of sociable numbers.

{?, ...}

A121507 Conjectured list of numbers whose aliquot sequence eventually reaches a cycle of length two or more.

{220, 284, 562, 1064, 1184, 1188, 1210, 1308, 1336, 1380, 1420, 1490, 1604, 1690, 1692, 1772, 1816, 1898, 2008, 2122, 2152, 2172, 2362, 2542, 2620, 2630, 2652, 2676, 2678, 2856, 2924, 2930, ...}

A121508 Conjectured list of numbers whose aliquot sequence eventually reaches a cycle of length two or more, but which are not themselves part of the cycle.

{562, 1064, 1188, 1308, 1336, 1380, 1420, 1490, 1604, 1690, 1692, 1772, 1816, 1898, 2008, 2122, 2152, 2172, 2362, 2542, 2630, 2652, 2676, 2678, 2856, 2930, 2950, 2974, 3124, 3162, 3202, 3278, ...}

A005114 Untouchable numbers, also called nonaliquot numbers: impossible values for sum of aliquot parts of

n

(A001065).

{2, 5, 52, 88, 96, 120, 124, 146, 162, 188, 206, 210, 216, 238, 246, 248, 262, 268, 276, 288, 290, 292, 304, 306, 322, 324, 326, 336, 342, 372, 406, 408, 426, 430, 448, 472, 474, 498, 516, 518, 520, 530, ...}

See also

• Index to OEIS: aliquot parts, sequences related to
• Sequence of the Day for July 27

External links

• Guy, Richard K.; Selfridge, J. L. (1975). “What Drives an Aliquot Sequence?”. Mathematics of Computation 29 (129): pp. 101–107. http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0384669-X/S0025-5718-1975-0384669-X.pdf.