Aliquot Sequence

What happens when you apply a simple, repetitive rule to the infinite set of integers? You might expect predictable patterns, but in the case of aliquot sequences, this simplicity gives rise to some of the most profound and enduring mysteries in number theory. An aliquot sequence is a journey through the numbers, where each step is determined by a single instruction: sum the divisors of your current number, excluding the number itself. This elementary process uncovers a hidden world of perfect numbers, sociable cycles, and baffling "runaway" sequences whose ultimate destiny is unknown. This article addresses the fundamental question: can we predict the fate of any number's journey?

The following chapters will guide you through this fascinating landscape. In "Principles and Mechanisms," we will define the aliquot map, explore the fundamental fates of termination and periodic cycles, and confront the great unsolved Catalan-Dickson conjecture. Then, in "Applications and Interdisciplinary Connections," we will examine the diverse "zoo" of sequence behaviors and uncover the surprising links between this simple iterative process, the frontiers of computer science, and even the famous Riemann Hypothesis.

Imagine the vast, infinite landscape of whole numbers. Pick one, any one. We are about to send it on a journey. There is only one rule for this journey, one map that every number must follow. This simple rule, when followed step by step, will lead us to some of the most elegant patterns, baffling behaviors, and profound unsolved mysteries in all of mathematics.

The rule is a function, a map that takes any number $n$ and tells us the next number to visit. We call this function the ​​aliquot sum​​, denoted as $s(n)$. It is defined with beautiful simplicity: ​​$s(n)$ is the sum of all the positive divisors of $n$, excluding $n$ itself​​. These are called the ​​proper divisors​​.

Let's take the number $12$ for a spin. What are its divisors? They are $1, 2, 3, 4, 6,$ and $12$. The proper divisors are all of these except for $12$ itself. So, we gather them up: $1, 2, 3, 4, 6$. The aliquot map tells us to sum them: $s(12) = 1 + 2 + 3 + 4 + 6 = 16$. So, from the location '12' on our number landscape, the map directs us to '16'.

Mathematicians often work with a related function called the sum-of-divisors function, $\sigma(n)$, which is the sum of all divisors, including $n$. From our example, you can see the relationship is straightforward: $\sigma(12) = 1+2+3+4+6+12 = 28$. The connection is always true: $\sigma(n) = s(n) + n$. Knowing this will become incredibly useful later on.

The sequence of numbers generated by applying this rule over and over—$n, s(n), s(s(n)), \dots$—is called an ​​aliquot sequence​​. It's a deterministic path through the world of numbers, with each step completely dictated by the last.

Let’s visualize this process. Imagine a giant directed graph where every non-negative integer is a point, a vertex. From each number $n$, we draw a single arrow pointing to its destination, $s(n)$. Since $s(n)$ always gives a unique result, every number has exactly one arrow leading away from it (an out-degree of 1). This isn't a random walk; it's a fixed, predetermined railway system across the integers. An aliquot sequence is simply the journey you take by following these railway tracks, starting from your chosen number.

What happens at the very beginning of the number line? What is $s(1)$? The only positive divisor of $1$ is $1$ itself. Since we must exclude the number itself, the set of proper divisors of $1$ is empty. By a fundamental and elegant convention in mathematics, the sum over an empty set is zero. So, $s(1) = 0$. This seemingly trivial point is actually a crucial feature of our landscape. It creates a final destination, a kind of "graveyard" for many sequences. If a journey ever arrives at the number 1, its very next step is to 0. And what's $s(0)$? By convention, we set $s(0)=0$, creating an absorbing state. Once you hit 0, you stay at 0 forever.

This gives us our first glimpse into the possible fates of these numerical journeys.

By starting with different numbers and following the tracks, we discover that not all journeys are alike. Three major destinies emerge.

Fate 1: Termination

Many sequences eventually arrive at the number 1, at which point they proceed to the 'graveyard' at 0 and terminate. Take any prime number, $p$. Its only proper divisor is $1$. So, $s(p)=1$. The very next step is $s(1)=0$. Thus, the aliquot sequence for any prime is a short, quick trip to oblivion: $p \to 1 \to 0$.

Composite numbers can have more interesting paths to termination. We saw that $s(12)=16$. What's next?

• $s(16)$: Proper divisors are $1, 2, 4, 8$. Sum is $15$.
• $s(15)$: Proper divisors are $1, 3, 5$. Sum is $9$.
• $s(9)$: Proper divisors are $1, 3$. Sum is $4$.
• $s(4)$: Proper divisors are $1, 2$. Sum is $3$.
• $s(3)$: Prime number! Sum is $1$.
• $s(1)$: Sum is $0$.

The full journey for 12 is $12 \to 16 \to 15 \to 9 \to 4 \to 3 \to 1 \to 0$. A winding path, but one that ultimately ends.

Fate 2: A Life in the Loop

Some numbers are not destined for termination. Instead, their journey leads them into a cycle, where they are doomed—or privileged—to repeat a sequence of steps for eternity. In our graph visualization, these are the closed loops of the railway.

• ​​Perfect Numbers (Period 1):​​ The simplest cycle is a self-loop. A number $n$ is called ​​perfect​​ if its journey from $n$ leads immediately back to $n$. That is, $s(n) = n$. The number is the sum of its own parts. The first perfect number is $6$, whose proper divisors are $1, 2, 3$, and indeed $1+2+3=6$. The aliquot sequence for 6 is an eternal stutter: $6, 6, 6, \dots$. This is a fixed point in our dynamical system, a cycle of length 1.

• ​​Amicable Numbers (Period 2):​​ Some numbers find a partner. Number $n$ leads to $m$, and $m$ leads back to $n$. This pair, $(n, m)$, is called ​​amicable​​. They are locked in a two-step dance for eternity. The smallest such pair is $(220, 284)$. Let's check: $s(220) = 284$ $s(284) = 220$ The sequence is $220, 284, 220, 284, \dots$. This is a cycle of length 2. Another lovely example is the pair $(1184, 1210)$.

• ​​Sociable Numbers (Period $k \ge 3$):​​ Why stop at pairs? There are larger "societies" of numbers that form longer cycles. For instance, the number $12496$ initiates a 5-member society: $12496 \to 14288 \to 15472 \to 14536 \to 14264 \to 12496, \dots$ These numbers form a sociable cycle of length 5, a larger loop on our grand railway system.

These three fates—termination, perfection, and sociability—cover a vast number of cases. It seems natural to ask: do they cover all of them?

This leads us to one of the great open questions in number theory: The ​​Catalan-Dickson conjecture​​. It proposes that every aliquot sequence eventually either terminates at 0 or enters a periodic cycle. In other words, the conjecture states that there is no third fate. There are no numbers whose journeys wander forever without repeating, growing larger and larger indefinitely. Every sequence is ultimately ​​bounded​​.

This seems like a reasonable guess. Yet, despite centuries of effort, no one has been able to prove it. What's more, there are sequences that make us doubt. Start with the number $276$. Its sequence has been calculated for thousands of steps, reaching numbers with hundreds of digits, and it has shown no sign of terminating or repeating. These are called ​​open​​ or ​​unresolved​​ sequences.

It is crucial to understand what this means. The existence of these incredibly long, growing sequences is not a counterexample to the conjecture. It's just evidence of how hard the problem is. The sequence for 276 might enter a cycle on its ten-thousandth step, or it might terminate after reaching a number with a million digits. We just haven't been able to compute far enough. These open sequences represent the frontier of our knowledge, taunting mathematicians with the possibility of a third, wild destiny: an infinitely growing, "runaway" sequence. Finding just one such sequence would disprove the conjecture and change our understanding of this simple system.

Why is it so difficult to predict the fate of a number like 276? The difficulty lies in the engine that drives the journey: the calculation of $s(n)$.

To compute $s(n) = \sigma(n) - n$, we need to compute $\sigma(n)$. And here is the catch: the only efficient way to compute $\sigma(n)$ for a large number $n$ is to first know its complete prime factorization. If $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, then $\sigma(n)$ can be found by a beautiful formula: $\sigma(n) = \sigma(p_1^{e_1}) \sigma(p_2^{e_2}) \cdots \sigma(p_k^{e_k}) = \left(\frac{p_1^{e_1+1}-1}{p_1-1}\right) \left(\frac{p_2^{e_2+1}-1}{p_2-1}\right) \cdots \left(\frac{p_k^{e_k+1}-1}{p_k-1}\right)$ You can see how this works for a simple case like a prime power, $p^k$. The sum of divisors is just $1+p+\dots+p^k$, a simple geometric series.

The problem is, finding the prime factors of a very large number is one of the hardest problems in computational mathematics. There is no known "easy" way to do it. The best general-purpose algorithm we have, the General Number Field Sieve, has a running time that grows in a "sub-exponential" way with the number of digits. This is fantastically better than trying every possible factor, but it is still slow enough that factoring a number with, say, 1000 digits is beyond our current global computing capacity.

This is the heart of the challenge. Each step in an aliquot sequence might produce a new, larger number. To take the next step, you must first solve a world-class hard problem: factoring that number. The simple, elegant rule of summing divisors has, hidden within it, a computational monster. This deep connection between a simple number game and the frontiers of computational complexity is a perfect example of the hidden unity and beauty in mathematics, where a childlike question can lead to the most profound challenges.

Having established the simple, almost childlike rule for generating an aliquot sequence—sum the proper divisors, and repeat—we now venture into the wild territory this rule creates. It is a journey that will take us from the finite to the potentially infinite, from ancient numerology to the frontiers of modern computation and the deepest unsolved problems in mathematics. It is a perfect illustration of how the simplest of seeds can blossom into a forest of staggering complexity and beauty.

If we think of each starting number as a "species," its aliquot sequence represents its life cycle. What we discover is a veritable zoo of different behaviors, a testament to the richness of the number world.

The most straightforward fate is termination. Many sequences, after a few steps, reach the number $1$. Since the only proper divisor of $1$ is... well, nothing, its sum of proper divisors is $0$. The sequence $1 \to 0$ comes to a definitive end. This is the fate of all prime numbers; for any prime $p$, its only proper divisor is $1$, so the sequence immediately becomes $p \to 1 \to 0$ and vanishes. Powers of two also exhibit this behavior in a particularly elegant way: the sequence starting with $2^k$ proceeds directly to $2^k - 1$, which is an odd number, and the chain continues from there, often towards a swift end. Many other numbers, like $12$, also trace a short path to oblivion: $12 \to 16 \to 15 \to 9 \to 4 \to 3 \to 1 \to 0$. These are the ephemeral creatures of our numerical zoo.

But not all sequences die out. Some achieve a form of immortality. The most famous are the ​​perfect numbers​​, which are fixed points of the aliquot map. For a perfect number $n$, we have $s(n) = n$. The sequence is a loop of length one: $n \to n \to n \to \dots$. The smallest such number is $6$, whose proper divisors ($1, 2, 3$) sum to $6$. The sequence is a placid $6, 6, 6, \dots$, a life of perfect solitude.

More complex are the sequences that enter a cycle of length two. These are the celebrated ​​amicable pairs​​. Here, two numbers are locked in a mutual embrace: $s(a)=b$ and $s(b)=a$. The sequence bounces back and forth between them for eternity: $a \to b \to a \to b \to \dots$. The pair $(220, 284)$ has been known since antiquity: $s(220) = 284$ and $s(284)=220$. This is not an isolated curiosity; other such pairs exist, like the larger couple $(2620, 2924)$.

Why stop at two? Nature, it seems, did not. There exist larger cycles, called ​​sociable numbers​​, where a group of integers form a closed loop. The first known example beyond an amicable pair is a remarkable, choreographed dance of five numbers discovered by Paul Poulet in 1918. Starting with $12496$, the sequence proceeds on a grand tour:

Each number hands the baton perfectly to the next, completing the circuit in five steps. These cycles represent the stable, social structures within our numerical ecosystem.

The predictable fates of termination and cycling do not tell the whole story. Some sequences appear to grow, reaching ever-larger numbers. A number $n$ is called ​​abundant​​ if the sum of its proper divisors is greater than itself, $s(n) > n$. Such numbers are the fuel for growth. For example, $36$, $48$, and $96$ are all abundant, and their sequences begin with a surge upwards.

What is the "engine" behind this growth? The answer lies in the multiplicative structure of the sum-of-divisors function, $\sigma(n)$. The condition for growth is $s(n) > n$, which is the same as $\sigma(n) - n > n$, or $\sigma(n)/n > 2$. The ratio $\sigma(n)/n$ is larger for numbers with many small prime factors. A large power of $2$, for instance, contributes a factor of $\sigma(2^k)/2^k = 2 - 1/2^k$, a value that gets very close to $2$. When combined with contributions from small odd primes like $3$ and $5$, the total ratio can easily exceed $2$, causing the sequence to grow.

Furthermore, certain combinations of prime factors can create a "driver" that tends to persist through iterations. For instance, if a number $n = 2^k m$ has an odd power of two (i.e., $k$ is odd) and is divisible by $3$, it turns out that its successor, $s(n)$, will also be divisible by $3$. This creates a stable structure that can support sustained growth across many steps.

This leads us to one of the greatest unsolved mysteries in this field, the ​​Catalan-Dickson conjecture​​. It asks: does every aliquot sequence eventually terminate or enter a cycle? Or could a sequence, like the one starting at $276$, grow indefinitely, wandering forever towards infinity? Despite monumental computational efforts, the fate of the sequence for $276$ (and many others) remains unknown. It is a simple question with an answer that has eluded mathematicians for over a century.

The pursuit of answers to questions like the Catalan-Dickson conjecture has transformed a corner of pure number theory into a field of experimental science. Discovering sociable cycles or tracking the mind-bogglingly long sequence for $276$ is impossible by hand. This is where number theory joins forces with ​​computer science​​. To explore these sequences, one needs efficient algorithms—first, to compute $s(n)$ for enormous numbers, and second, to detect if a sequence has entered a cycle. Computer scientists have developed clever methods, such as Floyd's "tortoise and hare" algorithm, which can detect a repeating loop without having to store the entire history of the sequence. Today, distributed computing projects harness the power of thousands of computers worldwide to push the boundaries of our knowledge, making this a true laboratory science.

Perhaps the most breathtaking connection is to one of the deepest problems in all of mathematics: the ​​Riemann Hypothesis​​. This famous conjecture, which concerns the distribution of prime numbers, has an astonishing consequence for aliquot sequences. Assuming the Riemann Hypothesis is true, a result known as Robin's inequality places a strict upper bound on the value of $\sigma(n)$. This, in turn, puts a "speed limit" on how fast an aliquot sequence can grow. Specifically, it implies that the growth factor from one step to the next, $a_{k+1}/a_k$, cannot grow faster than a very slowly increasing function of $a_k$, namely $\log\log a_k$.

This is a profound revelation. A question about the zeroes of a complex function, seemingly worlds away, dictates the potential behavior of a simple iterative process based on summing divisors. While it doesn't solve the Catalan-Dickson conjecture, it constrains the ways a sequence could possibly grow forever. It is a stunning glimpse into the hidden unity of mathematics, where disparate threads are woven together in a beautiful and unexpected tapestry—a fitting final thought on the surprising journey that begins with the simple act of adding up a number's friends.