Josephus Problem
17 Aug 2011

There are n persons in a circle, numbered 1 thru n. Going around the circle, every second person is removed from the circle, starting with person number 2, 4, and so on. Show that the number of the last person remaining in the circle can be obtained by writing n in binary, then moving the leftmost 1 to the right. So for example, with n = 13 persons (1101 in binary), the last person is number 11 (1011 in binary).


Classic problem found in introductory books on combinatorics.


Explained quite well in an article by Rick Regan. Also see the Wikipedia article and Wolfram's page.

Sloane A032434 contains the list of survivors given by the formula $latex 1 + 2n - 2^{1 + \lfloor\lg n floor}$ where $latex \lfloor n floor$ is the floor function and $latex \lg$ is the logarithm in base 2. The first few members of the sequence are 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1.

© Copyright 2008—2021, Gurmeet Manku.