Josephus Circular Elimination Recurrence

The Josephus problem is a mathematical puzzle describing a theoretical elimination game. A group of people stand in a circle and starting from a specified person, count around the circle by a fixed step. The person counted is removed, and the count continues from the next person until only one remains. This module visualizes the process and explores the recurrence relation that predicts the final survivor.

worked-example

Let's trace the elimination for 7 people with a count step of 3. We number the people 1 to 7. We start counting at person 1.

Initial circle: 1, 2, 3, 4, 5, 6, 7. Count 3 starts at 1. The 3rd person is 3. Remove 3.
Remaining: 1, 2, 4, 5, 6, 7. Count starts at 4. The 3rd person is 6. Remove 6.
Remaining: 1, 2, 4, 5, 7. Count starts at 7. The 3rd person is 2. (7, 1, 2). Remove 2.
Remaining: 1, 4, 5, 7. Count starts at 4. The 3rd person is 7. (4, 5, 7). Remove 7.
Remaining: 1, 4, 5. Count starts at 1. The 3rd person is 5. (1, 4, 5). Remove 5.
Remaining: 1, 4. Count starts at 1. The 3rd person is 1. (1, 4, 1). Remove 1.
Survivor: 4.

Alternatively, the zero-indexed recurrence is J(n, k) = (J(n-1, k) + k) mod n with J(1, k) = 0.
J(1, 3) = 0
J(2, 3) = (0 + 3) mod 2 = 1
J(3, 3) = (1 + 3) mod 3 = 1
J(4, 3) = (1 + 3) mod 4 = 0
J(5, 3) = (0 + 3) mod 5 = 3
J(6, 3) = (3 + 3) mod 6 = 0
J(7, 3) = (0 + 3) mod 7 = 3
Adding 1 for the 1-based index gives survivor 4, matching our trace.

experiment

In the interactive module, you can follow these steps to see the elimination process:

Set the People control to 7.
Set the Count step control to 3.
Set the Inspected removals control to 2 to pause the elimination process at intermediate steps.
Observe how the nextCountStartsAt value advances and how the eliminated labels are marked.

You can experiment directly in the Josephus Circular Elimination Recurrence module.

limitations

The visualization is limited to a small number of people to keep the diagram readable. The recurrence relation, however, is general and can calculate the survivor for very large groups in O(n) time, or even O(k log n) time when k is small compared to n. This module focuses on the deterministic recurrence and does not explore randomized counting out games.

references

Primary references and textbooks establishing the recurrence formula and theoretical bounds:

Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley Professional.
https://www-cs-faculty.stanford.edu/~knuth/gkp.html

Josephus Circular Elimination Recurrence