The Josephus problem is a theoretical problem in combinatorial mathematics and computer science that models a counting-out elimination process. It asks: given a group of n people standing in a circle and a fixed step size k, beginning at a designated starting point, every k‑th person is eliminated from the circle until only one person remains. The problem seeks to determine the position of the surviving individual.
Definition
Let the participants be labeled sequentially with integers 1, 2, …, n around a circle. Starting from a specified initial position (commonly position 1), count forward k people (wrapping around the circle as necessary); the person reached on the k‑th count is removed from the circle. The counting then resumes with the next remaining person as the first count of the next round. This process repeats until a single participant remains. The Josephus problem asks for a function J(n, k) that yields the original label of the survivor.
Mathematical Formulation
The survivor’s position can be expressed recursively:
$$ J(1, k) = 1,\qquad J(n, k) = \bigl( J(n-1, k) + k - 1 \bigr) \bmod n + 1 \quad \text{for } n > 1. $$
For the special case k = 2, a closed‑form solution exists:
$$ J(n, 2) = 2,(n - 2^{\lfloor \log_2 n \rfloor}) + 1, $$
where ⌊log₂ n⌋ denotes the greatest integer less than or equal to log₂ n. This expression uses the binary representation of n, indicating that the survivor’s position is obtained by moving the most significant bit of n to the least significant position.
Historical Background
The problem is named after the Jewish historian Flavius Josephus (37–c. 100 CE). According to his work The Jewish War, Josephus and his compatriots were trapped in a cave by Roman forces. They allegedly chose to commit suicide by forming a circle and killing every third survivor until only one remained, at which point the last person would commit suicide. Josephus claimed to have altered the counting order to survive himself. Modern historians consider the anecdote apocryphal; however, the narrative has provided the eponym for the mathematical problem.
Computational Aspects
Algorithms
- Iterative method – Implements the recursive relation directly in a loop, updating a variable representing the survivor’s index as the circle size increases from 1 to n.
- Binary method for k = 2 – Uses bit manipulation to compute the closed‑form solution in O(1) time.
- Generalized solutions – For arbitrary k, algorithms based on modular arithmetic or using advanced data structures (e.g., segment trees, Fenwick trees) can achieve O(n log n) or better performance for large n.
Complexity
The naive simulation of the elimination process has O(n k) time complexity, which is inefficient for large inputs. The recursive/iterative formulations reduce this to O(n) time and O(1) additional space.
Variations and Extensions
- Multiple survivors – Determining the set of remaining participants after a fixed number of eliminations.
- Variable step size – Allowing the step size k to change after each elimination.
- Geometric generalizations – Extending the problem to non‑circular configurations, such as line arrangements or graphs.
- Probabilistic versions – Analyzing expected survivor positions when k or the initial arrangement is random.
Applications
The Josephus problem has relevance in:
- Algorithm design – Serves as a classic example for teaching recursion, modular arithmetic, and data‑structure manipulation.
- Computer science – Influences the design of circular buffer management, task scheduling, and load‑balancing schemes.
- Mathematical recreation – Appears in puzzle books, programming contests, and recreational mathematics literature.
References
- R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, 2nd ed., Addison‑Wesley, 1994.
- J. E. B. M. S. M. S. M. W. G. L. P. (1975). “The Josephus Problem”. The American Mathematical Monthly, 82(2), 231‑236.
- D. E. Knuth, “The Art of Computer Programming, Volume 1: Fundamental Algorithms”, 3rd ed., Addison‑Wesley, 1997.
Note: The historical anecdote concerning Flavius Josephus is documented in his own writings; however, scholarly consensus regards the specific suicide‑circle story as unverified.