Aliquot Sum and Sequence

Introduction

The aliquot sum of a positive integer n is the sum of all proper divisors of n -- that is, all positive divisors of n excluding n itself. This function, denoted s(n), has been studied since antiquity and lies at the heart of number classification into perfect, abundant, and deficient numbers.

The aliquot sequence of n is formed by repeatedly applying the aliquot sum function: n, s(n), s(s(n)), s(s(s(n))), and so on. This sequence either terminates at 0, enters a cycle (such as a fixed point at a perfect number or an amicable pair), or -- as conjectured -- may grow without bound for certain starting values.

The study of aliquot sums connects to some of the oldest unsolved problems in mathematics, including the existence of odd perfect numbers and the behavior of the Catalan-Dickson conjecture.

Proper Divisors

A proper divisor of n is any positive divisor of n that is strictly less than n. For example, the proper divisors of 12 are 1, 2, 3, 4, and 6.

Finding Proper Divisors

procedure ProperDivisors(n): divisors = [1] // 1 is always a proper divisor for n > 1 for i from 2 to floor(sqrt(n)): if n mod i == 0: divisors.add(i) if i != n / i and n / i != n: divisors.add(n / i) return divisors

By iterating only up to the square root of n and collecting both i and n/i, we find all divisors in O(sqrt(n)) time.

The Aliquot Sum

The aliquot sum function s(n) is defined as:

s(n) = sum of all proper divisors of n = sigma(n) - n

where sigma(n) is the sum-of-divisors function (including n itself). For example, sigma(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28, so s(12) = 28 - 12 = 16.

Using Prime Factorization

If n = p1^a1 * p2^a2 * ... * pk^ak, then:

sigma(n) = product of (p_i^(a_i + 1) - 1) / (p_i - 1) for i = 1 to ks(n) = sigma(n) - n

For example, 12 = 2^2 * 3^1. sigma(12) = (2^3 - 1)/(2 - 1) * (3^2 - 1)/(3 - 1) = 7 * 4 = 28. s(12) = 28 - 12 = 16.

The sum-of-divisors function sigma is multiplicative: if gcd(a, b) = 1, then sigma(a * b) = sigma(a) * sigma(b). This property makes the prime factorization formula efficient for computing aliquot sums of large numbers.

Number Classification

Numbers are classified based on how their aliquot sum compares to the number itself:

Special Relationships

• Amicable numbers: A pair (a, b) where s(a) = b and s(b) = a. The smallest pair is (220, 284).
• Sociable numbers: A cycle of length k > 2 where s(n1) = n2, s(n2) = n3, ..., s(nk) = n1.
• Untouchable numbers: Numbers that are not the aliquot sum of any other number. Example: 2, 5, 52, 88.

Worked Examples

Computing s(220)

220 = 2^2 * 5 * 11

sigma(220) = (2^3 - 1)/(2-1) * (5^2 - 1)/(5-1) * (11^2 - 1)/(11-1) = 7 * 6 * 12 = 504

s(220) = 504 - 220 = 284

Computing s(284)

284 = 2^2 * 71

sigma(284) = (2^3 - 1)/(2-1) * (71^2 - 1)/(71-1) = 7 * 72 = 504

s(284) = 504 - 284 = 220

Therefore (220, 284) form an amicable pair: s(220) = 284 and s(284) = 220.

Computing s(496)

496 = 2^4 * 31

sigma(496) = (2^5 - 1)/(2-1) * (31^2 - 1)/(31-1) = 31 * 32 = 992

s(496) = 992 - 496 = 496

Since s(496) = 496, this is a perfect number. It equals 2^4 * (2^5 - 1) = 16 * 31, following Euclid's formula for even perfect numbers.

Aliquot Sequences

The aliquot sequence starting at n is: n, s(n), s(s(n)), s(s(s(n))), ... The sequence terminates when it reaches 0 (since s(1) = 0 and s(0) is undefined).

Examples of Aliquot Sequences

Starting at 10: 10, 8, 7, 1, 0 (terminates)Starting at 6: 6, 6, 6, ... (fixed point -- perfect number)Starting at 220: 220, 284, 220, 284, ... (amicable cycle)Starting at 276: 276, 396, 696, 1104, 1872, 3770, ... (unknown behavior)

The behavior of aliquot sequences is one of the great unsolved problems in number theory. The four possible behaviors are:

1. Termination at 0 (the most common case for small starting values)
2. Convergence to a perfect number (fixed point)
3. Entry into a cycle (amicable pair, sociable chain)
4. Unbounded growth (no known example is proven, but some sequences have been computed to very large values without terminating)

The Catalan-Dickson conjecture states that every aliquot sequence eventually terminates or enters a cycle. The conjecture remains unproven, and several sequences (notably those starting at 276, 552, 564, 660, and 966, known as the "Lehmer five") have been computed to enormous values without resolution.

Algorithms for Computing Aliquot Sums

Trial Division Method

procedure AliquotSum(n): if n <= 1: return 0 sum = 1 for i from 2 to floor(sqrt(n)): if n mod i == 0: sum = sum + i if i != n / i: sum = sum + n / i return sum

Prime Factorization Method

procedure AliquotSumPF(n): sigma = 1 temp = n for p from 2 to floor(sqrt(temp)): if temp mod p == 0: power = 1 while temp mod p == 0: temp = temp / p power = power * p sigma = sigma * (power * p - 1) / (p - 1) if temp > 1: sigma = sigma * (temp + 1) return sigma - n

Sieve-Based Method

To compute aliquot sums for all numbers up to N, use a sieve approach similar to the Sieve of Eratosthenes:

procedure AliquotSumSieve(N): s = array of size N+1, all zeros for i from 1 to N/2: for j from 2*i to N step i: s[j] = s[j] + i return s

This computes s(n) for all n from 1 to N in O(N log N) total time, which is much faster than computing each individually.

Complexity Analysis

For computing the aliquot sequence of a single starting value, each step costs O(sqrt(n)) where n is the current value. If the sequence grows (as in the case of 276), the values can become extremely large, making each step progressively more expensive.

Open Problems and Conjectures

Existence of Odd Perfect Numbers

All known perfect numbers are even and have the form 2^(p-1) * (2^p - 1) where 2^p - 1 is a Mersenne prime. It is unknown whether any odd perfect number exists. If one does exist, it must be greater than 10^1500 and satisfy many additional constraints.

Are There Infinitely Many Perfect Numbers?

It is conjectured (but unproven) that there are infinitely many even perfect numbers. This is equivalent to conjecturing that there are infinitely many Mersenne primes. As of 2024, only 51 Mersenne primes are known.

The Guy-Selfridge Conjecture

Richard Guy and John Selfridge conjectured that the Catalan-Dickson conjecture is false -- that is, some aliquot sequences grow without bound. This remains unproven in either direction.

The aliquot sequence starting at 276 has been computed past 10^200 without terminating or entering a cycle. Whether it eventually does so remains one of the most intriguing open questions in elementary number theory.

References

• Guy, R. K. "Unsolved Problems in Number Theory." Springer, 3rd edition, 2004, Section B2.
• Dickson, L. E. "History of the Theory of Numbers, Volume I: Divisibility and Primality." Carnegie Institution, 1919.
• Erdos, P. "On Amicable Numbers." Publicationes Mathematicae Debrecen, vol. 4, 1955, pp. 108-111.
• te Riele, H. J. J. "Perfect Numbers and Aliquot Sequences." Computational Methods in Number Theory, Part I, Mathematisch Centrum, 1982, pp. 141-157.
• Pomerance, C. "On the Distribution of Amicable Numbers." Journal fur die reine und angewandte Mathematik, vol. 293, 1977, pp. 217-222.
• Lenstra, H. W. "Perfect Numbers." Nieuw Archief voor Wiskunde, vol. 23, 1975, pp. 168-181.