The Josephus Problem

Picture $n$ people standing in a circle, numbered 1 through $n$. Starting from person 1, you count off every $k$-th person and remove them, continuing around the circle (skipping already-removed people) until only one survivor remains. The question: for given $n$ and $k$, which starting position survives?

Simulating it directly — actually walking around a circle removing every $k$-th person — works but is slow for large $n$. The elegant approach uses a recurrence: if $J(n)$ is the (0-indexed) surviving position among $n$ people counting by $k$, then after the first removal you have $n-1$ people left, and the problem restarts on that smaller circle, just relabeled. The recurrence is $J(1) = 0$ and $J(n) = (J(n-1) + k) \bmod n$ for $n > 1$. Each step solves the smaller problem, then maps its answer back onto the original numbering by shifting by $k$ positions and wrapping around with the modulus.

For example, with $k=2$ (every second person eliminated) and $n=5$ people: $J(1)=0$, $J(2)=(0+2)\bmod 2=0$, $J(3)=(0+2)\bmod3=2$, $J(4)=(2+2)\bmod4=0$, $J(5)=(0+2)\bmod5=2$. So the 0-indexed survivor is position 2, meaning person 3 (1-indexed) survives — which matches direct simulation: eliminating 2, 4, 1, 5 in order leaves 3.