Mathwords logoMathwords

Josephus Problem — Definition, Formula & Examples

The Josephus Problem is a counting puzzle where nn people stand in a circle and every kk-th person is eliminated until one survivor remains. The goal is to determine the position of that last person standing.

Given nn people labeled 1,2,…,n1, 2, \ldots, n arranged in a circle, with every kk-th person removed sequentially, the Josephus function J(n,k)J(n, k) returns the position (using 0-indexed labeling) of the survivor. It satisfies the recurrence J(n,k)=(J(n−1,k)+k) mod nJ(n, k) = (J(n-1, k) + k) \bmod n with base case J(1,k)=0J(1, k) = 0.

Key Formula

J(n,k)=(J(n−1,k)+k) mod n,J(1,k)=0J(n, k) = (J(n-1, k) + k) \bmod n, \quad J(1, k) = 0
Where:
  • nn = Total number of people in the circle
  • kk = Every k-th person is eliminated
  • J(n,k)J(n,k) = 0-indexed position of the survivor

How It Works

Start at person 1 and count around the circle. Every kk-th person is removed, and counting resumes from the next person. The circle shrinks by one each round until a single person remains. For the special case k=2k = 2, a closed-form solution exists using the binary representation of nn. For general kk, you apply the recurrence relation bottom-up from J(1,k)=0J(1,k) = 0 up to J(n,k)J(n,k), then convert to 1-indexed by adding 1.

Worked Example

Problem: Seven people stand in a circle numbered 1 through 7. Every 3rd person is eliminated. Which position survives?
Base case: With 1 person, the survivor is at position 0.
J(1,3)=0J(1, 3) = 0
Build up: Apply the recurrence for each value of nn from 2 to 7.
J(2,3)=(0+3) mod 2=1J(2,3) = (0 + 3) \bmod 2 = 1
Continue: Keep applying the formula step by step.
J(3,3)=(1+3) mod 3=1,J(4,3)=(1+3) mod 4=0J(3,3) = (1+3) \bmod 3 = 1, \quad J(4,3) = (1+3) \bmod 4 = 0
Finish: Complete the remaining steps.
J(5,3)=(0+3) mod 5=3,J(6,3)=(3+3) mod 6=0,J(7,3)=(0+3) mod 7=3J(5,3) = (0+3) \bmod 5 = 3, \quad J(6,3) = (3+3) \bmod 6 = 0, \quad J(7,3) = (0+3) \bmod 7 = 3
Convert to 1-indexed: Add 1 to convert from 0-indexed to 1-indexed position.
3+1=43 + 1 = 4
Answer: Person in position 4 is the last survivor.

Why It Matters

The Josephus Problem appears in discrete mathematics and algorithms courses as a classic example of solving problems via recurrence relations. It also illustrates how modular arithmetic governs cyclic structures, a pattern that arises in circular buffer management and round-robin scheduling in computer science.

Common Mistakes

Mistake: Confusing 0-indexed and 1-indexed positions in the final answer.
Correction: The recurrence J(n,k)=(J(n−1,k)+k) mod nJ(n,k) = (J(n-1,k) + k) \bmod n produces a 0-indexed result. Add 1 at the end if the problem labels people starting from 1.