The Count That Spared Him

In the summer of 67 CE the Roman legions took the fortress town of Yodfat, in Galilee. Their commander was a Jewish general named Yosef ben Matityahu, who would later write the war down for his conquerors under the name we know him by: Flavius Josephus. As the town fell he hid in a pit with forty other men of standing. Rather than be taken alive, they resolved to die by each other's hands, and to leave the order to chance. Josephus, who did not want to die, came out of that pit alive. He tells us how in his own Wars of the Jews, and he is careful about exactly how much he is willing to explain.

“Come on, let us commit our mutual deaths to determination by lot. He whom the lot falls to first, let him be killed by him that hath the second lot, and thus fortune shall make its progress through us all; nor shall any of us perish by his own right hand.” Josephus, Wars of the Jews, III.8.7 (Whiston translation)

They agreed. Men laid their necks bare in turn. And then the sentence Josephus writes about himself, which does the work of an entire alibi in a single clause:

“yet was he with another left to the last, whether we must say it happened so by chance, or whether by the providence of God.” Josephus, Wars of the Jews, III.8.7 (Whiston translation)

He and one other man were the last two standing. He persuaded that man to live, and they surrendered. Whether the lots really fell that way, or Josephus arranged to be standing in the right place, he leaves for you to decide. Centuries later, mathematicians took the second possibility seriously and asked the clean version of the question: if the killing goes strictly around a circle, removing every k-th person, which seat is the safe one? That question has a beautiful answer, and it is the rest of this page.

The instrument

Run the circle

Here are n people in a circle, seat 1 at the top. Counting starts at seat 1, and every k-th person is removed; the count carries on from the next living seat and wraps around. Set the two dials, then step through it or let it run. The last seat glowing is the one the count spares.

The shortcut

When the count is every second person, the answer is a single bit

Leave the dial at every 2nd and something strange happens. Line up the survivor's seat as you raise the crowd, and you get this: 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1…. The answer keeps climbing by twos and then, without warning, collapses back to 1. It resets to 1 at exactly the powers of two: 2, 4, 8, 16, 32. That is the fingerprint of binary.

Write the crowd size n in binary. To find the safe seat, take the leading 1 and move it to the end. That is the whole trick. If n = 13 = 1101, then rolling the top bit to the bottom gives 1011 = 11, and seat 11 is the one that lives. Try it against the circle:

The reason is a short induction. Point at the first person, seat 1, and remove seat 2, then 4, then 6, all the even seats, once around. If the crowd was even, you come back to seat 1 having wiped out exactly half, and you are looking at the same problem again with half as many people, all sitting on odd seats. Peel that halving off enough times and the leading bit is what falls away first; the rest of the bits, shifted up one place with a fresh 1 tacked on, spell the survivor. Written as arithmetic: if n = 2^p + L with L the leftover after the biggest power of two, the safe seat is 2L + 1. Same fact, two costumes.

The general rule

Other counts have no such gift

Move the dial off every-2nd and the tidy bit-trick evaporates: for a general step k there is no known shortcut that beats simply walking the circle. But you never have to rebuild the whole ring to add one more person. If you know the safe seat for a circle of m − 1, then adding one person shifts it by exactly k, modulo the new size. Counting from zero: J(1) = 0, and J(m) = (J(m − 1) + k) mod m. Add one to land back on human seat numbers. That single line is the general answer, and it is the one the panel below runs to check the circle for thousands of crowd sizes and steps at once.

The legend, measured

Forty-one in the cave

The puzzle is usually told as Josephus's own: forty-one men in a ring, every third one killed, and Josephus clever enough to stand where he would be spared. Run exactly that, 41 seats and every 3rd removed, stopping when two are left, and the survivors are seats 16 and 31. Take it all the way to a single winner and it is seat 31. So the story has a satisfying answer, and the numbers are real.

But here is where the honesty has to come in, because it is easy to let the tidiness of the answer pretend to be history. Josephus never describes a circle, and never describes every third man. His text says they drew lots. The count of forty companions is his (“he met with forty persons of eminency that had concealed themselves”), which with Josephus makes forty-one, and that is the only number the puzzle borrows from the record. The ring, the fixed step of three, and the seats 16 and 31 are the mathematicians' construction, laid over the story long afterward. They are true about the construction. They are not a transcript of what happened in the pit, and the man who wrote the pit down made sure we could never quite tell.