Overview
The puzzle is named after the historian Flavius Josephus, who — by his own account — survived a Roman siege by standing in exactly the right place in a suicide circle.
How to solve The Josephus Problem
- Simulate once to see the shape of it: the first sweep removes every even seat.
- After that sweep you face the same puzzle with half as many people, so the answer recurses.
- Write n = 2^m + L with 0 ≤ L < 2^m. The survivor is 2L + 1: for n = 10 = 8 + 2 that is seat 5.
The key insight
In binary the answer is a one-bit rotation: write n in binary and move the leading 1 to the end. 10 = 1010₂ becomes 0101₂ = 5. Powers of two are the fixed points — if n = 2^m the survivor is always seat 1.
Variations & echoes
- For a general step k the recurrence is J(n) = (J(n−1) + k) mod n, computable in O(n) with no closed form.
- The same elimination structure appears in round-robin scheduling and in circular buffers.
Frequently asked questions
Does the answer change if counting starts elsewhere?
Only by a rotation: the survivor's seat shifts by the same offset, because the circle has no distinguished point beyond where you start counting.