1002 The Josephus problem and its generalization
Theorem 37.1.Letf(n)be the survivor in the Josephus problem ofn
prisoners.
f(2n)=2f(n)− 1 ,
f(2n+1)=2f(n)+1.Example
f(100) =2f(50)− 1
=2(2f(25)−1)−1=4f(25)− 3
=4(2f(12) + 1)−3=8f(12) + 1
=8(2f(6)−1) + 1 = 16f(6)− 7
=16(2f(3)−1)−7=32f(3)− 23
=32(2f(1) + 1)−23 = 64f(1) + 9
=73.There is an almost explicit expression forf(n):if 2 mis the largest
power of 2≤n, then
f(n)=2(n− 2 m)+1.Corollary 37.2.The binary expansion off(n)is obtained by transfer-
ring the leftmost digit 1 ofnto the rightmost.
f(100) =f(1100100 2 ) = 1001001 2 =64+8+1=73.