The Josephus problem

Unsolved Medium Archive

archive posted 13 Jun 2026

$n$ people numbered $1$ to $n$ stand in a circle. Going around the circle starting from person 1, every second person is removed (first person 2, then 4, and so on, continuing around the circle) until one person remains. Find a formula for the position $J (n)$ of the survivor.

Posed by folklore (after a story told by Flavius Josephus)

Like0

combinatorics recurrences

History and references

Solved by folklore.

The problem is named after the first-century historian Flavius Josephus, who wrote that he and one other man were the last two left when a group trapped in a cave chose to die one by one rather than surrender. After one trip around the circle all even positions are gone and the problem repeats with about half as many people, which gives $J (2 n) = 2 J (n) - 1$ and $J (2 n + 1) = 2 J (n) + 1$ . Solving these, if $n = 2^{m} + l$ with $0 \leq l < 2^{m}$ then $J (n) = 2 l + 1$ . In binary this is a cyclic shift of the digits of $n$ one place to the left. For other step sizes there is a simple recurrence, and the step 2 case is treated in detail in Graham, Knuth and Patashnik's Concrete Mathematics.

References

Josephus problem (Wikipedia)

Solutions 0

Nobody has posted a solution here yet. Solutions written on Problempedia are credited to the people who write them.

References

Solutions 0

Discussion 0