The sum of the parts, taken again

A perfect number is one whose proper divisors add back to itself. That definition invites an obvious experiment, which is to take a number that is not perfect, add up its proper divisors, and see what happens to the answer. Twelve’s divisors below itself are 1, 2, 3, 4 and 6, which make sixteen. Sixteen’s make fifteen. Fifteen’s make nine; nine’s make four; four’s make three; three’s make one; and one has no proper divisors at all.

That walk is the aliquot sequence of twelve, from the old word for a proper divisor. Writing $s(n)$ for the sum of the proper divisors of $n$ — which is $\sigma(n) - n$ in the notation of the divisor rectangle — the sequence is $n, s(n), s(s(n)), \dots$ A perfect number is a sequence that stands still. The question of what every other sequence does has been open since 1888, and it is the kind of question that looks like the Collatz problem because it is one: a simple arithmetic rule, iterated, whose long-run behaviour nobody can predict.

Four ways to end, and a fifth #

A sequence can reach one, and then zero, and stop. It can reach a perfect number and stay there forever. It can reach a pair of numbers each of which is the other’s divisor sum, and alternate between them. It can close a longer cycle. And, as far as anybody can prove, it can climb forever.

The cycles are rarer and stranger than the perfect numbers. The amicable pair 220 and 284 was known to the Pythagoreans. The cycle through 12496, 14288, 15472, 14536 and 14264 was found by Paul Poulet in 1918 — the first sociable chain — along with one of length twenty-eight starting at 14316, which remains the longest known. Chains of length four, five, six, eight, nine and twenty-eight exist; no chain of length three has ever been found, and none has been ruled out.

Every one of those endings is a case of an orbit that has to come back if the orbit stays bounded: finitely many values below any ceiling, so a bounded sequence must eventually repeat, and a repeat traps it in a cycle. The only way to avoid all four endings is to grow without bound. Whether any sequence does is the whole question.

A thousand starting points #

The natural first step is to run every small starting value and see.

The small print of the grid repays reading. The three that enter the amicable pair are 220, 284 and 562 — and 562 is there because it is twice the prime 281, so its proper divisors are 1, 2 and 281 and they add to 284, one step from the pair. Of the nineteen that land on a perfect number, only 6, 28 and 496 are perfect themselves; the other sixteen are numbers like 95, whose divisors 1, 5 and 19 add to 25, whose divisors add to 6. Every one of those sixteen reaches its perfect number in a handful of steps, and none of them passes through anything large. Below a thousand, at least, landing on a fixed point is something that happens early; the sequences that wander far are the ones that end at 1 or do not end.

The thirteen that pass the figure’s bound are not thirteen independent mysteries. Many merge: 306 reaches 396 and then follows 276’s route, and several of the others join one another within a few steps. Traced back to where they first meet, the open cases below a thousand come from five distinct sequences — 276, 552, 564, 660 and 966, known as the Lehmer five after the family that pushed them furthest by hand and early computer.

Twelve of the thirteen are exactly the starting values below a thousand that remain undecided today. The thirteenth, 840, climbs past $10^{22}$ and is known from much longer computations to come back down; the figure’s bound is simply too low to see it. That is a small, precise illustration of the difficulty. A bound in the computation can never distinguish a sequence that climbs forever from one that climbs for a long time, and the history of this problem is a succession of sequences that were thought to be unbounded until a few thousand more terms were computed.

276 has been followed for more than two thousand terms, through numbers of more than two hundred digits, and it is still climbing. Each new term needs the factorisation of the previous one, and factoring a two-hundred-digit number is a serious computation — so the sequence advances at the speed of the best factoring methods available, which is what the effort to decide it has mostly been an effort in.

Parity decides the population a sequence lives in #

Before asking what pushes a sequence up, it is worth asking why odd starting values almost never appear in the list of hard cases. Every one of the thirteen above is even, and that is not a coincidence of small numbers.

The reason is a parity fact about $\sigma$. The divisor sum of a prime power $q^e$ with $q$ odd is $1 + q + \cdots + q^e$, a sum of $e+1$ odd numbers, which is odd exactly when $e$ is even. The divisor sum of $2^e$ is $2^{e+1} - 1$, always odd. Multiplying these together, $\sigma(n)$ is odd exactly when every odd prime in $n$ appears to an even power — which is to say, when $n$ is a square or twice a square.

So $s(n) = \sigma(n) - n$ has the same parity as $n$ unless $n$ is a square or twice a square, and in that case the parity flips. Squares and twice-squares are sparse — fewer than $2\sqrt{N}$ of them below $N$ in all — and a sequence of large numbers almost never hits one. An even sequence stays even and an odd sequence stays odd, apart from rare accidents like twelve’s walk through the square 16 and on to the odd 15.

That matters because the two populations behave completely differently. About a quarter of all numbers are abundant, with $s(n) > n$, but the abundant numbers are overwhelmingly even. The first odd abundant number is 945, and only about one odd number in two hundred and fifty is abundant. An odd sequence therefore sits among numbers that almost always shrink, and it falls; an even sequence sits among numbers that overshoot about half the time, and whether it rises or falls is genuinely in the balance. The hard cases are even because that is where the balance is.

Neither half of this is new to the problem — it is the perfect-number rectangle again, whose rows are divisor sums of prime powers, read for their parity. It is the reason every serious computation on these sequences concentrates on even starting values, and the reason the drivers below all contain a power of two.

A long climb that comes down #

The sequence that shows why nobody trusts a computation is 138.

Nothing in the first eighty steps suggests the sequence will ever stop, and nothing in the next thirty suggests it will turn around. Its peak, 179,931,895,322, is more than a million times its start. Then it descends almost as steadily as it rose, and ends.

This is the pattern that gives the problem its character. A sequence’s local behaviour — rising for twenty steps, falling for five — says almost nothing about its eventual fate, because each step depends on the factorisation of the current term, and factorisations of neighbouring large numbers have almost nothing to do with each other. The climb is not a trend. It is a sequence of independent-looking coin flips, each biased by the shape of one number’s divisors.

What makes a sequence climb #

Guy and Selfridge, in 1975, asked what drives a sequence upward, and the cleanest answer they found involves perfect numbers directly.

Take the perfect number $28 = 4 \times 7$ and multiply it by an odd number $m$ that shares no factor with 7. Because $\sigma$ is multiplicative and 4, 7 and $m$ share no factors,

$$\sigma(28m) = \sigma(4)\,\sigma(7)\,\sigma(m) = 7 \cdot 8 \cdot \sigma(m) = 56\,\sigma(m),$$

so the next term is

$$s(28m) = 56\,\sigma(m) - 28m = 28\,\big(2\sigma(m) - m\big).$$

Three things follow from that one line. The next term is again 28 times something. That something, $2\sigma(m) - m$, is odd, because $m$ is odd and $2\sigma(m)$ is even. And it is at least $m$, because $\sigma(m) \ge m$. So the next term is at least as large as this one, and it is again 28 times an odd number.

The same calculation works for every even perfect number $P = 2^{k-1}(2^k - 1)$: a term of the form $P$ times an odd number coprime to $2^k - 1$ produces a next term that is again $P$ times an odd number, and no smaller. The perfect number sits in the factorisation like a ratchet. Guy and Selfridge called it a driver, and the drivers built from perfect numbers are the ones whose action can be proved in a line.

The table shows the driver arriving and holding. At step 7 the term is $2 \cdot 5^2 \cdot 61$ and the next is smaller. At step 8 the factorisation acquires exactly $2^2 \cdot 7$, and from then on the ratio of each term to the one before is at least one on every row the driver holds. The ratio is sometimes very close to one — at steps 23 and 24 the odd part is prime, $\sigma(m) = m + 1$, and the sequence creeps up by 56 — and sometimes more than two, when the odd part has many small factors of its own.

How a driver is lost #

The ratchet has one way to slip, and the table shows it happening. The argument needed the odd part $m$ to share no factor with 7. If $2\sigma(m) - m$ happens to be divisible by 7, the next term is $28$ times a multiple of 7 — its factorisation contains $7^2$ — and the calculation above no longer applies.

At step 20 exactly that happens: the term is $2^2 \cdot 3^2 \cdot 7^2 \cdot 31$. The next term still turns out larger, and at step 21 the driver is back, but nothing guaranteed either. At steps 26 and 27 the power of seven rises again, to $7^2$ and then $7^3$, and whether the sequence keeps its factor of exactly $2^2$ is now a matter of the parity of divisor sums rather than of a proof.

So a driver is sticky, not permanent. Each step it survives unless a new factor of 7 appears, and a new factor of 7 appears about one step in seven if $2\sigma(m) - m$ behaves like a random odd number modulo 7. Surviving the escape at step 20 was luck. Losing the driver does not end the climb either — a term with a different power of two may acquire a different driver, or none — but a driver-free term with a single factor of 2 and no factor of 3 tends to shrink, and in Guy and Selfridge’s analysis that lone factor of 2 is the one downdriver — the only configuration that reliably pulls a sequence down.

The picture of 276’s first hundred steps is the driver argument made visible. Almost every stretch of growth is shaded; the gaps are the steps where a power of seven has crept in, and the sequence climbs through them only because the driver comes back.

Two conjectures that cannot both be right #

Eugène Catalan conjectured in 1888 that every aliquot sequence is bounded — that each ends at one, at a perfect number, or in a cycle. Leonard Dickson restated it in 1913 and the claim is usually called the Catalan–Dickson conjecture. It is the natural first guess, and it is the analogue of the Collatz conjecture’s claim that every orbit comes down.

Guy and Selfridge, armed with the driver analysis, conjectured the opposite in 1975: that many sequences are unbounded, and that among sequences starting from even numbers the unbounded ones might even have positive density. Their reasoning is the heuristic above made quantitative. A driver multiplies the term by at least one at each step and often by more; it survives each step with probability about six in seven; and a sequence that holds a driver for long enough grows so large that the chance of ever returning to small numbers becomes negligible.

Neither side has a proof. No sequence has been shown to be unbounded, and no sequence currently climbing has been shown to be bounded. The only partial result of real strength points in Guy and Selfridge’s direction: Erdős showed in 1976 that for any fixed number of steps $k$, almost every abundant starting value produces a sequence that increases for all of its first $k$ steps. That says nothing about forever, and forever is the question.

The comparison with the Collatz problem is closer than an analogy. There too the best theorem is a statement about almost every starting value over a limited horizon — almost every number comes down at least somewhat, in Tao’s sense — and there too the statement about every starting value over all time is untouched. Both problems have a heuristic that predicts the answer with great confidence and a structure that defeats every attempt to turn the heuristic into a proof, and both have a smallest undecided case that has been computed far past any size where a counterexample could be recognised by eye.

What the pictures cannot show #

The fates grid decides 986 of 999 starting values and draws the other thirteen as undecided at a bound of $10^{22}$. That is a statement about the computation, and one of the thirteen — 840 — is undecided only because the bound is low. The grid cannot distinguish a sequence that is unbounded from one that has not come down yet, and nor can any grid.

The driver argument is proved for terms that are exactly a perfect number times an odd number coprime to it, and only for those. The shaded stretches in the pictures are where the hypothesis holds; the unshaded steps are where it fails, and nothing in the argument says what happens there. The picture of 276 climbing through a gap is evidence that the driver usually comes back, not a proof that it must.

And the sequences drawn are the ones small enough to compute to the end or to a bound. The question the conjectures are about lives in sequences hundreds of digits long, where each step costs a hard factorisation, and where the shape of a factorisation — which is all that decides the next step — is exactly the thing no picture of a number’s size can display.

Where the factor of seven comes from #

The escape condition, $7 \mid 2\sigma(m) - m$, deserves one more look, because it shows why these sequences feel random without being random.

Whether 7 divides $2\sigma(m) - m$ depends on $m$ modulo 7 and on $\sigma(m)$ modulo 7, and $\sigma(m)$ modulo 7 depends on the residues of every prime factor of $m$ modulo 7 and on their exponents — for a prime $q$, $\sigma(q) = q + 1$, so $\sigma$ adds one to $q$’s residue. Nothing about this is random. But $m$ is the odd part of a number that was itself produced by a divisor sum, and its prime factors are, to any test anybody has devised, as unpredictable as the prime factors of a number picked at random of the same size.

That is the same source of apparent randomness as in the walk Pollard used to factor: a completely deterministic rule, applied to arithmetic that scrambles residues, produces sequences that pass every statistical test while remaining impossible to analyse. Proving anything about the long-run behaviour of an aliquot sequence would require controlling the factorisation of the terms, and there is no known method for controlling the factorisation of numbers produced by an arithmetic rule — which is the same obstacle as in proving there are infinitely many Mersenne primes.

Still open: whether any sequence climbs forever #

The Lehmer five — 276, 552, 564, 660 and 966 — are the smallest starting values whose sequences have not been decided, and each has been pushed through numbers of well over a hundred digits. The question for each is binary and unanswered: does it eventually fall, or not?

Beyond them is the structural question. Is there any unbounded aliquot sequence? A proof would need a mechanism that keeps a driver in place forever, or a growth argument that survives the driver’s occasional loss; a disproof would need a reason every driver must eventually be lost and every sequence must eventually find its way back down. The perfect-number drivers give a clean proof of growth for one step at a time and nothing at all about the step at which a new factor of the Mersenne prime appears.

A property of one number, iterated #

The question began as a curiosity about perfection, and the aliquot sequences turn it into something else. A single number’s divisor sum is a finite computation with a definite answer. The same computation applied to its own output is a dynamical system on the whole numbers, and dynamical systems defined by arithmetic have a way of becoming undecidable in practice long before anyone can show they are undecidable in principle.

What is striking is how directly the original objects return. The perfect numbers are the fixed points of the map. The amicable pairs and sociable chains are its periodic orbits. And the perfect numbers turn up a second time, disguised as factors, as the mechanism that pushes sequences upward — so that the numbers which stand perfectly still under the map are also what keeps the most interesting sequences from ever standing still at all.