# Tag Info

## Hot answers tagged josephus-problem

17

This is known as the Josephus problem. If the number of people $n$ is expressed as $n=2^m+p$, with $m$ as large as possible, the survivor is in seat $2p+1$ Another way to express it is to write $n$ in binary and rotate left one position. For example, let there be $19$ people at the table, so we write $19=2^4+3$ and the winner is $2\cdot 3+1=7$, or $19_{... 4 As mentioned in the previous thread, this is the (generalized) Josephus problem, known as such because the oldest known reference (at least in Western history) is by the historian Flavius Josephus. There is no known general closed form. You can compute the position of the survivor by recurrence:$\$p_s^n = \begin{cases} 1 + (p^{n-1}_s - 1 + s) \bmod n &...

Only top voted, non community-wiki answers of a minimum length are eligible