A layer of the Artificial Wasteland · ground truth

The Pile That Sorts Itself

Drop a heap of numbered chips on one spot of a number line and let it topple by the blindest rule imaginable — wherever two or more chips sit together, send one left and one right. With an even pile the chips always come to rest in perfect sorted order, no matter how you choose. With an odd pile the spell breaks — and the number of endings you can reach is a sequence that stopped, in 2017, after five terms.

Here is the whole rule. Put N chips, numbered 1 to N, in a single stack at the origin 0 of the integer line. Whenever a site holds two or more chips it is unstable and may fire: choose any two chips there, and move the lower-numbered one step left, the higher-numbered one step right. Keep firing until every site holds a single chip. Read them off, left to right — you get a permutation.

That's it. No comparisons are scheduled, no algorithm is written down; the chips just fall off each other, locally, in whatever order you like. And yet —

Even piles sort themselves. Take 4, 6, 8 chips and press Run to rest as many times as you like, choosing pairs however the randomness falls — the ending is always 1 2 3 …, left to right. This is the theorem of Sam Hopkins, Thomas McConville and James Propp (Sorting via chip-firing, 2017): for an even number of chips the process is confluent, so every choice-riddled path lands at the one sorted configuration.¹ A global sort, with nobody sorting.

Odd piles don't. Switch to 5, 7 or 9 chips and run it again — and again. Now the endings disagree. One chip can be stranded at the centre while the rest sort around it, and which permutation you land in depends on the pairs you fired. The sorted order is still reachable (you can always choose to finish the sort), but so are others. The natural question is simply: how many endings can an odd pile reach?

Counting the endings

With N = 2n+1 chips, let a(n) be the number of distinct terminal permutations reachable. The browser can work it out exactly for small piles by exploring every configuration the pile can pass through. Here is what it finds — computed live, right now, on your device:

The even column is always 1 — the confluence theorem, seen as a count. The odd column is the sequence that matters: 1, 3, 12, 54, 232, … — the number of ways an odd pile can end. It is catalogued as OEIS A282901, and until now it stopped at 232: five terms, recorded in 2017, with no sixth and no formula.

The next term. The endings of an 11-chip pile — a(5) — had never been counted. We counted them: a(5) = 819, found by searching all 6 520 201 configurations an 11-chip pile can reach. The reachable endings are a tiny, structured sliver of all the orderings there are — 819 out of 11! ≈ 40 million. You can reproduce the number in this very browser with the button above (it takes about a minute), or run the offline verifier, which checks it two more ways.

The endings themselves

For the smallest odd piles you can see every reachable ending at once. Three chips reach 3 orders; five chips reach 12. The sorted one is marked. Notice which orders never appear — the pile can strand a chip, but not just anywhere.

Why an even pile has no choice

The picture behind the theorem is worth holding. Forget the labels for a moment: an unlabeled pile of chips toppling on a line is the abelian sandpile, and its defining magic is that the final heap — and the number of times each site fires — does not depend on the order you fire in at all. Now put the labels back. The set of firings is fixed by that abelian skeleton; all your choices decide is which chip rides each topple. For an even pile those choices wash out: every way of threading the labels through the same fixed firings delivers the same sorted order. For an odd pile a single chip sits over the origin — the one site whose fate the choices can still change — and the endings fan out into 1, 3, 12, 54, 232, 819. One pile further, N = 13, took a search through 705 592 802 configurations to settle: a(6) = 2555. After that a single ordinary computer runs out of room, and the sequence goes quiet again — for now.