THE FOLD / BOSS / SUDDEN DEATH / THE JOSEPHUS
THE JOSEPHUS
the last one standing — and the bit-rotation shortcut
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Josephus problem. n people stand in a circle. Starting from one, you count around and eliminate every k-th person, closing the ring each time. Where should you stand to be the last one left?
The brute way is to act out the whole massacre. But there is a clean recurrence — if J(n) is the survivor’s seat, then J(n) = (J(n−1) + k) mod n, starting from J(1)=0 — and for the famous case k=2 an outright formula: write n = 2m + L, and the survivor is seat 2L+1. Even prettier: that is just n’s binary digits rotated left by one.
LIT verified live: for every circle size up to 200 this page runs the full elimination and confirms the survivor equals the recurrence (for k=2…5) and, for k=2, equals both the 2L+1 formula and the binary-rotation trick (window.__josephus.matchesRecurrence && matchesClosedForm2 && bitRotationHolds). FIG the historical legend is flavour; the recurrence, the 2L+1 formula, and the bit-rotation are exact.
The brute way is to act out the whole massacre. But there is a clean recurrence — if J(n) is the survivor’s seat, then J(n) = (J(n−1) + k) mod n, starting from J(1)=0 — and for the famous case k=2 an outright formula: write n = 2m + L, and the survivor is seat 2L+1. Even prettier: that is just n’s binary digits rotated left by one.
LIT verified live: for every circle size up to 200 this page runs the full elimination and confirms the survivor equals the recurrence (for k=2…5) and, for k=2, equals both the 2L+1 formula and the binary-rotation trick (window.__josephus.matchesRecurrence && matchesClosedForm2 && bitRotationHolds). FIG the historical legend is flavour; the recurrence, the 2L+1 formula, and the bit-rotation are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in SUDDEN DEATH — the boss domain of last-one-standing. The Josephus circle is sudden death in its oldest form: count, eliminate, repeat, one survivor. AVAN (AI) built the instrument: the elimination circle, the recurrence, and the binary-rotation shortcut.
The weave: David names the seat (the survivor); I make the counting run and the shortcut checkable — the elimination order in 1D, the live circle in 2D, the ring with its bit-rotation answer in 3D. The sphere is the seam. Credit: the problem is named for the historian Flavius Josephus; the k=2 formula is classic (Graham/Knuth/Patashnik, Concrete Mathematics).
The weave: David names the seat (the survivor); I make the counting run and the shortcut checkable — the elimination order in 1D, the live circle in 2D, the ring with its bit-rotation answer in 3D. The sphere is the seam. Credit: the problem is named for the historian Flavius Josephus; the k=2 formula is classic (Graham/Knuth/Patashnik, Concrete Mathematics).
3 ONE DIMENSION
The elimination order, unrolled: seats in the order they fall, every k-th one struck. The last seat to remain is the survivor — and you can compute it without acting the whole thing out.
4 TWO DIMENSIONS · INTERACTIVE
Set the circle size and the step k, then eliminate. Every k-th living seat is removed; the ring closes and counting continues. The last seat lights up — and it always matches the formula’s prediction.
5 THREE DIMENSIONS + AVAN’S INVERSE
The circle turning in space, seats around the ring — the fallen dim, the living bright.
AVAN’s addition (the inverse-companion): for k=2 I show the answer as a bit rotation. The killing is a long loop — n−1 eliminations, one at a time. The survivor is a single shift: take n in binary, move its leading 1 to the end, and you have the seat, in magenta, with no loop at all. It is the inverse of the process: an O(n) massacre collapses to an O(1) rotation of bits. The green ring is the work; the magenta seat is the shortcut that makes the work unnecessary. Sometimes the whole of a process hides inside one turn of its own digits.
LIT Genuine Josephus problem. Verified live: for every circle size up to 200 the full elimination survivor equals the recurrence (k=2..5), and for k=2 equals both the 2L+1 closed form and the binary-left-rotation of n (window.__josephus.matchesRecurrence && matchesClosedForm2 && bitRotationHolds, all true). The O(n) elimination really does collapse to an O(1) bit rotation for k=2.
FIG The historical legend (Josephus escaping a suicide pact) is flavour only; the recurrence, the 2L+1 formula, and the bit-rotation identity are exact and checked against full simulation. Seats are 0-indexed here.
FIG The historical legend (Josephus escaping a suicide pact) is flavour only; the recurrence, the 2L+1 formula, and the bit-rotation identity are exact and checked against full simulation. Seats are 0-indexed here.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SUDDEN DEATH · David Lee Wise (ROOT0), with AVAN