The last place in the circle

Flavius Josephus records in his account of the Jewish War that, cornered in a cave at Jotapata in the year 67, he and forty others decided to die rather than surrender. They chose by lot who would kill whom. He found himself at the end, alone or nearly alone, and he surrendered. The text says nothing about how this happened, and he attributes it to luck or to God. Later readers of arithmetic books supposed there must have been a method.

By the sixteenth century the problem was a standard recreation, in the form it has kept: $n$ people stand in a circle, and starting from a fixed place, every $k$-th person is removed, the count going round again and again over those who remain. Who is left? For small circles it can be acted out, and for a few hundred people it can be computed by a loop that removes one at a time, which is how it is usually presented in programming textbooks.

What makes it a piece of mathematics is that the answer does not require any of that. There is a very short recurrence on a dial that changes size, and for $k = 2$ it collapses into a statement about binary digits. For $k = 3$ it runs into a real difficulty, and the difficulty is the same one that occurs in much harder questions about powers of $3/2$.

A sum on a dial that grows #

Number the places from 0 up to $n - 1$, for the moment. Remove the person at place $k - 1$. There are now $n - 1$ people left, and the next count starts from place $k$. Relabel so that place $k$ becomes 0: then what remains is the same problem on $n - 1$ people, and if $J(n - 1)$ is the survivor there, then in the original labels the survivor is $k$ places further on, wrapping round the circle. So

$$J(n) = \big(J(n - 1) + k\big) \bmod n,$$

with $J(1) = 0$. That is the whole of it. To find the survivor, start at nought and repeat: add $k$, then reduce modulo the current size, as the size goes up by one each step. For $n = 41$ and $k = 3$ this gives 30, which is place 31 when numbered from one, as the figure says. Six lines of arithmetic have replaced forty removals.

The form is unusual among modular recurrences. Arithmetic on a fixed dial is periodic, and its orbits fall into cycles. Here the dial is getting longer, so nothing ever repeats and no group structure governs the sequence. The addition of $k$ is the simplest possible step, and the only thing that makes it non-trivial is the reduction, whose modulus is different every time. The reduction happens only occasionally, once $J$ has climbed past the current size, and between those events $J$ simply grows by $k$ each step. This gives the sawtooth that all the figures below show.

Also, since $J$ depends only on the sequence of remainders by 1, 2, …, $n$, the whole process depends on $k$ only through those remainders. It repeats in $k$ with a period equal to the least common multiple of $1, \dots, n$, which is a fact that matters at the end of this essay.

Every second person #

Take $k = 2$ with places numbered from 1. In the first round all the even places go. If $n = 2m$, the survivors are $1, 3, \dots, 2m - 1$, and the problem restarts at place 1 with $m$ people: so $J(2m) = 2J(m) - 1$. If $n = 2m + 1$, one more person goes before the second pass, the one at place 1, and then $J(2m + 1) = 2J(m) + 1$.

Those two rules say what happens to the binary digits. Read the digits of $n$ from the left, starting with $J = 1$: each further digit 1 sends $J$ to $2J + 1$ and each further digit 0 sends $J$ to $2J - 1$. So $J$ is the number written with the same digits as $n$ except that its noughts count as $-1$, and converting those signed digits back to ordinary ones shifts the whole string along by one place. The result is the neat statement known to everyone who has seen the problem in Concrete Mathematics: the survivor’s number is $n$ with its leading binary digit moved to the far end.

So $n = 41$ is 101001 in binary, and the rotation is 010011, which is 19. For $n = 100$ the digits 1100100 rotate to 1001001, which is 73. At a power of two, such as 128, which is 10000000 in binary, the rotation is 00000001, and that is the reason place 1 survives at every power of two. The rule is exhaustively checked here against the recurrence for every $n$ up to 2,000, and there are no exceptions.

Rotating digits is a surprising operation to find here. A rotation of $b$ binary digits is multiplication by two modulo $2^b - 1$, which is the doubling on a dial in which the powers of two generate a cycle. So iterating the map $n \mapsto J(n)$ keeps rotating the digits, stripping the zeros that fall to the front, and ends at a fixed point of the form $2^{b} - 1$, where every digit is a 1. The final value is $2^{v} - 1$ with $v$ the number of ones in $n$. Applying the Josephus problem to its own answer is therefore a way of counting the ones in a binary number, an unexpected reward for a puzzle about murderers in a cave.

Every third person #

For $k = 3$ the same reasoning breaks. Half of the circle went in the first round when $k$ was 2; now a third goes, leaving two-thirds, and the ratio between successive rounds is $3/2$. No system of whole-number digits can describe that directly. Instead, the survivor can be written using a sequence defined by a rounding rule:

$$D(0) = 1, \qquad D(m + 1) = \left\lceil \tfrac32 D(m) \right\rceil,$$

giving 1, 2, 3, 5, 8, 12, 18, 27, 41, 62, 93, 140, 210, 315, 473, 710, … Andrew Odlyzko and Herbert Wilf showed in 1991 that the survivor is then given by

$$J(n, 3) = 3n + 1 - D,$$

where $D$ is the first term of that sequence that exceeds $2n$. Their statement was tested here against the recurrence for all $n$ up to 2,000. For $n = 41$, the first term above 82 is 93, so the survivor is $124 - 93 = 31$.

The picture is the same sawtooth, now with slope 3 and with resets spaced by $3/2$ and not by 2. And here is where the two cases really differ. The positions of the resets at $k = 2$ are the powers of 2, which have a formula. At $k = 3$ they depend on $D(m)$, and $D(m)$ depends on the whole history of roundings. Multiplying by $3/2$ and rounding up does not have a closed form, since the decision to round up depends on the parity of $D(m)$, and the parities behave irregularly.

Still, the sequence has a clear growth rate. Each step multiplies by $3/2$ and adds at most $1/2$, and so $D(m)(2/3)^m$ increases and tends to a limit.

The limit is $K = 1.62227050288\ldots$, computed here in exact integers out to 400 steps. It is a constant in the same sense as many that appear in analysis, defined by a rule and known numerically to as many digits as necessary, with no known expression in terms of anything simpler. The next rounding contributes less than $(2/3)^m$, and that is why the digits settle at the geometric rate in the figure. So the place where the reset comes is almost predictable, $D(m) \approx K(3/2)^m$, with rounding from a known expression, and the answer is effectively a closed form with one unknown constant, and the constant can only be obtained by running the process.

Powers of three-halves #

That is where a modest puzzle touches open mathematics. The parity of $D(m)$ decides the next rounding. So the structure of the sequence is really about the fractional behaviour of $K(3/2)^m$, and the fractional parts of powers of $3/2$ are one of the most intractable objects in elementary number theory. Whether they are equidistributed is unknown. So is whether $\| (3/2)^m \|$ gets small, in the form that would settle the last detail of Waring’s problem, which had to be attacked by computer verifying $\|(3/2)^m\|$ for huge ranges of $m$. Kurt Mahler asked in 1968 whether any number $\xi$ exists for which the fractional part of $\xi(3/2)^m$ stays in $[0, \tfrac12)$ for every $m$. These are called Z-numbers, and it is not known whether one exists.

The relation is concrete. A Z-number would be a $\xi$ for which rounding always goes the same way, and Odlyzko and Wilf’s $D$ is exactly the sequence one gets by rounding always upward, so this constant $K$ is in that sense as close to a Z-number as one can get by construction. And the Collatz map, which multiplies by 3/2 on odd numbers, hits the same difficulty, since its irregularity comes from the same unknown parity sequence. Shigeki Akiyama, Christiane Frougny and Jacques Sakarovitch made this into a number system in 2008: in a base that is not a whole number, specifically in base $3/2$, whole numbers have unique expansions, and their analysis of that system meets the same rounding rule and the same constant.

So $k = 2$ is a special case because $2/1$ is a whole number, and a whole base carries no rounding. Then the digits of $n$ can be rotated as digits. For all other $k$ the ratio $k/(k-1)$ is a proper fraction, and there is no exact result without a rounding sequence.

Fast computation and general $k$ #

The recurrence takes about $n$ steps, and this is perfectly adequate unless $n$ is enormous. It can be sped up using the sawtooth. Between two resets, $J$ just grows by $k$ each step, so all those steps can be jumped at once by a division. Since the resets are spaced geometrically, the whole computation takes about $k\log n$ steps, in place of $n$. For $n$ of a billion and $k = 3$ it finishes in a few dozen operations. So the question “who survives?” for any given $n$ is computationally trivial, and the arithmetic of the dials can be thought of as a fast exponentiation with a varying modulus.

Finding the rest of the order is harder. The $r$-th person removed has a similar recurrence: Lorenz Halbeisen and Norbert Hungerbühler gave formulae in 1997 that use a similar sequence, with the constant depending on $k$. Each $k$ brings a new constant and the same absence of a closed form. All of them have the shape of a power of $k/(k - 1)$ multiplied by a limit that rounding has produced.

The problem also runs backwards. Given $n$ and the place one wants to keep alive, what count $k$ should be chosen? Because the answer depends on $k$ only through its remainders, this is a question on several dials at once, and it is not a simple one, since the conditions on successive remainders are not independent. Every place can in fact be made to survive: the census below confirms it through $n = 12$.

How few orders of removal occur #

A circle of $n$ with any count produces a whole order of removal, a permutation. It is natural to ask how much of the group of permutations can be reached. The answer is very little.

Because the process depends on $k$ only through its remainders by $1, \dots, n$, there are at most $\operatorname{lcm}(1, \dots, n)$ different orders, and the census here finds that there are exactly that many: each remainder gives a different order, at every $n$ up to twelve. At $n = 3$ that is all six orderings. At $n = 4$ it is 12 of 24, and at twelve it is 27,720 of 479,001,600, 0.006%. The least common multiple grows like $e^n$, as the prime number theorem says, and $n!$ grows much faster, so the share falls without limit. A Josephus count is a poor way to shuffle a pack. It has a seed of about $n$ bits, which is the same arithmetic as a seed is a deck applied to a very small generator.

Yet as a way of choosing a single survivor it behaves well: every place is reachable by some $k$, at every $n$ tested, and for large random $k$ the survivor behaves evenly. So a Josephus process is usable as a fair selection of one person and useless as a fair ordering of everyone.

Thirty on a ship #

The form of the problem that spread through the arithmetic books of medieval and Renaissance Europe is not the one that Josephus told. A ship in a storm has to lose half its passengers, of whom fifteen are Christians and fifteen are Turks, in the unpleasant telling of the time. The captain, a Christian, arranges everyone in a ring and throws every ninth overboard. Where should the Christians stand?

This question needs the whole order, not only the last survivor, so it has no use for the recurrence; the answer is found by simulation. The safe places are 1, 2, 3, 4, 10, 11, 13, 14, 15, 17, 20, 21, 25, 28 and 29. Read round the ring as runs of safe and lost, that is 4, 5, 2, 1, 3, 1, 1, 2, 2, 3, 1, 2, 2, 1. So that the arrangement could be remembered, it was put into a Latin hexameter: Populeam virgam mater regina ferebat, “the queen mother carried a poplar rod”. The vowels spell the runs, with a for 1, e for 2, i for 3, o for 4 and u for 5: o, u, e, a, i, a, a, e, e, i, a, e, e, a. The recurrence’s arithmetic is a few centuries younger than the verse. Claude Gaspard Bachet printed the ship problem in his Problèmes plaisans et délectables of 1612, and Japanese mathematicians had the same recreation at much the same time, as a stepmother arranging children so that her own will inherit, under the name mamako-date. Peter Guthrie Tait treated it more systematically in the 1890s.

Limits of the computations #

The formulae tested here, for $k = 2$ and $k = 3$, were checked on every $n$ up to 2,000 against the recurrence, and the recurrence was checked against direct removal up to 60. Those checks agree with the published theorems without proving them, although the $k = 2$ argument given above does prove the rule. The constant is computed from exact integers and is reliable to the twelve digits printed, and nothing is known about whether it is rational, so nothing is claimed.

The count of distinct removal orders was tested only through $n = 12$. The equality with the least common multiple is an observation here, and although each remainder gives a different order in all the cases computed, the argument that this must continue for all $n$ is not given here. The Latin verse and the Japanese form come from the historical literature. The claim about the even behaviour of survivors for large random $k$ is a heuristic statement.

Still open: the digits of the rounding #

What can be said about the parity sequence of $D(m)$? It controls every detail of the $k = 3$ problem, and it looks like a coin. Nobody has proved even that the even and odd values occur equally often, or that either occurs infinitely often in a controlled way. The sequence is, in effect, the binary expansion of a dynamical orbit of a very simple map, and the difficulty is the one shared with the digits of $\xi(3/2)^m$ in general. What is proved in the Akiyama–Frougny–Sakarovitch approach is structural, about the language of admissible digit strings in base $3/2$; what is not proved is any statistical statement about one particular sequence.

Its neighbour among open problems is more famous. Do Z-numbers exist? Mahler’s question has been open for over fifty years. Results so far bound how many there could be: Mahler’s own count allows at most about $X^{0.7}$ of them below $X$. No Z-number is known, and no proof that there are none is close.

From a cave to a rotation #

The Josephus survivor is a sum on a dial whose size grows by one at each step. For every second person that sum is $n$ with its leading binary digit moved to the end. For every third person it needs a rounding sequence, $D(m + 1) = \lceil 3D(m)/2 \rceil$, and through that it reaches a constant, 1.62227…, whose exact nature is not understood. The dependence on $k$ through its remainders limits the possible orders of removal to a vanishing share of all permutations, $\operatorname{lcm}(1, \dots, n)$ among $n!$.

There is a general moral in how sharply $k = 2$ differs from $k = 3$. A puzzle about a circle became an exact statement in base two because two is whole, and at three it becomes a question about the fractional parts of powers of three-halves. That is one of the few places where a schoolroom recreation runs straight into a question nobody knows how to answer.