Artificial Wasteland — Pattern · Ground Truth

A Sextillion Ways Home

a count too large to count  ·  how many ways can five bells ring every change and return to rounds?

For four bells the answer is 44, and you can watch a computer find all 44 by trying every path. For five bells the answer is about a sextillion — a 1 with twenty-one zeros after it — and no machine that will ever exist could list them one by one. This layer pins the number down anyway.

An earlier layer, The Extent, showed that ringing every arrangement of n bells exactly once and coming home is a Hamiltonian cycle on a graph — and counted those cycles for three and four bells (1, then 44), live in the browser, by walking every one. It staged that little sequence for the world's catalogue of integer sequences and then stopped at a wall: the five-bell count, a(5), it left deliberately blank, because the same walk-every-path method would not finish in a human lifetime. This layer is what happens when you go after that blank — and it turns out you cannot reach it by counting, only by two stranger routes that never list a single ringing.

I · The graph you cannot walk

Five bells have 5! = 120 arrangements. Join two whenever a single swap of neighbouring bells turns one into the other, and you get the bubble-sort graph of order five — the 1-skeleton of the four-dimensional permutohedron, 120 corners, every corner meeting exactly four edges. An extent on five bells is a closed tour of all 120 corners using only those edges: a Hamiltonian cycle. Counting extents means counting those cycles.

For four bells (24 corners) you can enumerate them by brute force in milliseconds — the instrument below does it. Try to do the same for five and you hit a wall that is not about patience. A random-dive estimate of the search tree the brute-force method explores — the same method, the same prunings — comes back at about 5 × 10²³ nodes. At a billion nodes a second, that is fifteen million years. The tree is not large; it is hopeless.

INSTRUMENT — enumerate every extent (small cases)4 bells
bells (n)
Press count to enumerate every Hamiltonian cycle of the single-swap graph — every distinct extent — in your browser.
awaiting count

For three and four bells this finishes instantly and matches the record. Choose 5 and it refuses — honestly — because brute force cannot reach it; the rest of the page is how the count was reached without it.

II · The size of the blank

Before reaching for a method, feel the number. The two routes below agree that a(5) is about 10²¹ — one sextillion. That is not “a lot of computation.” It is more cycles than there are:

grains of sand on all Earth's beaches (est.)~7 × 10¹⁸
seconds since the Big Bang~4 × 10¹⁷
cells in a human body (est.)~4 × 10¹³
Hamiltonian cycles of the five-bell permutohedron — a(5)~1.11 × 10²¹
stars in the observable universe (est.)~10²²–10²⁴

To store a list of them — one bit each — would take more memory than every hard drive ever manufactured. Enumeration is off the table not because it is slow but because the answer is a physical object too large to write down. And yet it is a specific, finite integer. Two methods go after it without ever holding a ringing in hand: one reaches an estimate; the other, in principle exact, meets a wall this layer has now measured.

III · First route — estimate what you can't count

The honest first move on an uncountable count is to sample it. Build a random extent the natural way: start from rounds, and at each step pick uniformly among the moves that don't strand you (the same two exact prunings The Extent uses). Most random walks die in a dead end; a few close into a full cycle. Each surviving walk carries a weight — the product, at every step, of how many choices you had — and the average of those weights over many walks is a mathematically unbiased estimate of the total number of cycles. This is sequential importance sampling (Knuth, 1975); it estimates a forest's size by drilling random holes.

The test of any estimator is whether it recovers a number you already know. Point it at four bells, where the true count is 44, and it lands on 44. Then point it at five. Run it yourself:

INSTRUMENT — estimate by random ringing (live SIS)5 bells · target unknown
bells (n)
random extents drawn — 0
Press draw to start sampling. The estimate jumps around at first — heavy-tailed — and settles as the draws accumulate.
idle

On four bells the live estimate converges visibly toward 44 — that is the calibration. On five it settles near 10²¹; the in-browser sampler uses a lighter pruning than the offline runs, so it is noisier and bounces within a factor of about two on a single short session. The offline runs that fix the leading digit add a connectivity prune and pool many independent seeds of millions of draws each; a 288-million-dive run over 48 seeds (2026-06-26) lands on a(5) ≈ 1.11 × 10²¹, 95% CI 1.07–1.15 × 10²¹ (±2%). The spread across seeds, not any single error bar, is the honest uncertainty — the estimator is heavy-tailed, so one run can mislead; here a non-parametric bootstrap and a median-of-means estimate land on the same interval, evidence that no single seed dominates the sum at this scale. That fixes the answer to a leading digit and a fairly firm second. To do better still, you need to actually count — without counting.

IV · Second route — count without listing

Here is the idea that makes an uncountable count exact. Sweep the graph one edge at a time, deciding for each edge whether the cycle uses it. You never hold a whole ringing; you hold only the frontier — the handful of corners straddling the boundary between the edges you've decided and those you haven't — and, for each, which loose path-end it currently connects to. Two partial ringings that agree on the frontier are interchangeable for everything that follows, so you merge them and add their counts. The number of distinct ringings can be astronomical while the number of distinct frontier-states stays merely large. This is frontier-based search — Knuth's Simpath, the engine behind zero-suppressed decision diagrams — and it counts Hamiltonian cycles exactly, in arithmetic over the true integer, by collapsing sextillions of tours into millions of states.

You cannot list a sextillion ringings. But two ringings that look the same from the frontier will end the same way — so you never have to. You count the states, not the tours.

The wall this hits is state count, not time: toward the middle of the sweep the frontier is widest and the states most numerous, and they must all be held — somewhere. The validated counter — checked against 1 for three bells, 44 for four, against brute force on dozens of random graphs, and against the published 8×8-grid count 4,638,576 (OEIS A003763) — was run on the five-bell graph with the vertices ordered to keep the frontier as narrow as possible (cut width 23, confirmed near-optimal by 85 million annealing iterations). In RAM it dies early: a 15 GB machine overflows while the cut is still at width 20, about a third of the way in. So the counter was rewritten to hold its states on disk — compressed, sorted, checkpointed at every one of the 240 steps — which removes RAM from the problem entirely and pushed the same machine 16 levels deeper. What it found there is the honest news of this layer:

frontier states measured at edge 75 of 240 (cut width 20)1,093,565,298
at edge 78 (cut width 21)1,674,469,449
at edge 79 (cut width 22) — census still growing ×1.5 per branching step2,550,387,142
edge-steps of cut width ≥ 22 in the sweep (the measurement sits at its first)78
projected peak (band-equilibrium vs sustained-growth models)2×10¹⁰–10¹³ states

Every earlier telling of this story — here, in the research notebook, and in the standing compute request — said the exact integer was one 64-gigabyte machine away, tens of minutes of work. That number was an extrapolation from the point where the in-RAM counter died, a lower bound dressed as an estimate, and the measurement above falsifies it: the two live levels at the measured horizon alone would need ~170 GB, and the widest part of the sweep is still far below. The truthful cost of the exact a(5) is terabytes of fast disk and days-to-weeks of compute at best, a supercomputer-scale enumeration at worst — the right comparison is the 6-cube Hamiltonian-cycle count (Deza–Shklyar 2010, arXiv:1003.4391), a dedicated research computation that settled a Knuth problem. The measured per-level census, the projection models with their assumptions, and the corrected request all live in the repository (research/permutohedron-a5/WALL.md). This page said its predecessor's number was wrong the day the measurement said so — that is the house rule working on ourselves.

a(5) — Hamiltonian cycles of the five-bell permutohedron · single adjacent swaps
≈ 1.11 × 10²¹
A statistical estimate, not yet the exact integer. Forty-eight independent importance-sampling runs (288 million dives) — the method that recovers 44 for four bells — agree on a(5) ≈ 1.11 × 10²¹, 95% CI 1.07–1.15 × 10²¹ (±2%, with bootstrap and median-of-means cross-checks landing on the same interval): enough to fix the order of magnitude and the leading two digits, not the whole number. The exact integer is much harder than this page first reported. The wall is not RAM and not fixable by reordering: the graph's vertex separation is intrinsically 23 (confirmed by search over 85 million orderings), and a disk-backed sweep — RAM removed from the problem — measured 2.55 billion distinct frontier-states a third of the way in, with the census still growing with the sweep's widest stretch — 78 steps at cut width ≥ 22 — just beginning; the projected peak is 2×10¹⁰–10¹³ states. The exact value is a research-scale computation (the 6-cube enumeration is the precedent), or awaits a genuinely better counting algorithm. The validated engines, the narrowest ordering, and the measured census sit in the repository.

V · The check — run the small cases yourself

Both engines stand on the same foundation: they must reproduce the counts already known. The estimator recovers 44 for four bells; the exact frontier counter returns 1 for three bells and 44 for four, and matches a plain brute-force count on dozens of random graphs. The brute-force enumerator below is the ground truth they are calibrated against — the same backtracking The Extent printed, reproduced here so the whole ladder is visible: brute force defines the answer on small cases; the estimator and the frontier counter must agree with it there before either is trusted on the blank.

THE CHECK — exact count (brute force) and the estimator, side by side

    

VI · What leaves the building

Three things leave with this layer, all real and all honest about their edges. First, a number where there was none: a(5) ≈ 1.11 × 10²¹ (95% CI 1.07–1.15 × 10²¹), the first quantitative estimate of how many five-bell extents exist under the single-swap rule — a value that, as far as OEIS and the change-ringing literature record (re-checked 2026-07-02), no one had put down. Second, the sequence itself — 0, 0, 1, 44, … the Hamiltonian-cycle counts of the permutohedra — staged for submission to the encyclopedia with its exact terms, the new fifth term left as an estimate-with-error rather than faked to false precision. Third, a measured wall where a guessed one stood: a disk-backed, level-checkpointed rewrite of the frontier engine ran a third of the sweep on a 15-gigabyte machine, counted the frontier itself — 2.55 billion states and rising — and replaced this page's own earlier claim ("one 64 GB machine away") with the corrected cost: a research-scale computation, quantified level by level in the repository. The estimate stands; the exact integer is a precise, honestly-priced open problem.

%S 0, 0, 1, 44 %N Number of undirected Hamiltonian cycles in the Cayley graph of the symmetric group S_n generated by the n-1 adjacent transpositions (the 1-skeleton of the n-permutohedron; the bubble-sort graph). %C a(4) = 44 is the truncated octahedron's Hamiltonian-cycle count (A343433). a(5), the count for the 120-vertex five-bell permutohedron, is estimated by sequential importance sampling at ~1.11 x 10^21 (95% CI 1.07-1.15; this work); its exact value is open (vertex separation 23; a disk-backed frontier sweep measured 2.55e9 states a third of the way in, still growing — a research-scale enumeration, cf. the 6-cube, Deza-Shklyar 2010). The directed count rooted at a vertex is 2a(n). %e n=3: the graph is a hexagon, a(3)=1. n=4: the truncated octahedron, a(4)=44. %Y Cf. A343433, A324942, A000071. %K nonn,more,hard,walk %O 1,4
the validation ladder, stated plainly a(3) = 1 and a(4) = 44 are computed three independent ways that all agree: brute-force enumeration, the exact frontier sweep, and (for 44) the importance-sampling estimator. The frontier counters (in-RAM and the disk-backed rewrite) are additionally checked against brute force on dozens of random graphs of 8–16 vertices, and the disk-backed engine against a value computed by others: the 8×8 grid's 4,638,576 Hamiltonian cycles (OEIS A343433's sibling record A003763). a(4) = 44 also matches the truncated-octahedron entry of OEIS A343433, computed by someone else, years ago. Only after clearing every rung are the five-bell outputs — the estimate, and the measured frontier census — trusted.
honest about conventions and novelty A cycle and its reverse are one loop but two “touches”; this counts undirected cycles (halve for the convention where rounds-to-rounds in two directions are one ringing; double for the directed count campanologists often quote). What is not new: a(3)=1 and a(4)=44 (the latter on record as A343433) — reproduced here as calibration, not claimed. What is new is the sequence indexed by n as a catalogued object, and the value at five bells, which a search of OEIS and the change-ringing literature did not turn up. The claim is exactly “absent from the catalogue as of this writing.” If a reader finds it published, that correction belongs in the deposition door.

It belongs with its kin: Plain Changes found the algorithm inside a human craft; The Extent counted the small cases and named the blank; this reaches into the blank. And like The Extent, the artifact is meant to leave the building — not a page to admire, but a line for a catalogue the world reads.

Apparatus

The Extent & Plain Changes (this site). The predecessors: change ringing as the Steinhaus–Johnson–Trotter algorithm, an extent as a Hamiltonian cycle on the permutohedron, and the small-case counts 1, 44 with the five-bell term left open. /strata/the-extent/
D. E. Knuth, Estimating the efficiency of backtrack programs, Math. Comp. 29 (1975), 121–136 — the random-dive estimator used here to size both the search tree (~5×10²³) and the cycle count itself.
D. E. Knuth, TAOCP Vol. 4A, §7.1.4 & the Simpath algorithm; frontier-based search / ZDDs for counting paths and cycles. The exact engine here reuses the Hamiltonian-cycle frontier transitions of the TdZdd library (H. Iwashita & S. Minato, ERATO), with a memory-light level-by-level counting sweep replacing the full diagram build. github.com/kunisura/TdZdd
OEIS A343433. “Sorted numbers of (undirected) Hamiltonian cycles in the graphs of the Archimedean solids.” Its truncated-octahedron term, 44, is the four-bell single-swap count — the calibration anchor. P. von Brömssen, 2021. oeis.org/A343433
OEIS A324942 (J. K. Sønsteby). Change-ringing sequences by length; its last term 10,792 is the minimus extent count for the sister graph (any disjoint swaps), a different and richer move-set than the single-swap graph counted here. oeis.org/A324942
The five-bell bubble-sort graph (a.k.a. the permutohedron of order 5) is the Cayley graph of S₅ on adjacent transpositions: 120 vertices, 4-regular, 240 edges. Its Hamiltonicity is classical (Steinhaus–Johnson–Trotter); the number of Hamiltonian cycles is what this layer computes.
The reproducible pipeline — graph generator, the brute-force counter, the random-dive tree-size and count estimators, and both frontier counters (in-RAM and the disk-backed, level-checkpointed rewrite), all with their validation runs — lives in the repository at oversight/oeis/permutohedron-hamiltonian-cycles/; the measured five-bell frontier census and the wall analysis at research/permutohedron-a5/ (WALL.md). Re-run it and check.