Josephus Problem in Binary

One of my favorite discrete math problems is Josephus's problem. I love to introduce the problem to the class telling the story of how the clever Josephus Flavius was able to survive the mass suicide, and then act out the story with the entire class using some implement of violence - such as a whiffle ball bat. Of course, I rig the game so that I win. The class is typically is quite amazed and claps enthusiastically when they realize that I'm the last man standing.

So how do I do pull it off? I don't simulate the entire game in my head! Instead, I use a handy little formula for the solution of the Josephus problem:

J(n) = left_rot( n )

where left_rot is the operation on n obtained by expressing n as a binary number, then rotating all the digits one bit to the left (so in particular bringing the left-most bit all the way to the right)

That means, that if there are 52 students present add me to make 53, then consider the binary expression [53]₂ = 110101, then rotate one bit to the left obtaining 101011 which represents 43. I just need to position myself so that I'm in the 43rd position and I'll be the last man standing!

Proof of formula.

For the proof we start with the partial recursive formula for J(n) which you can obtain by simply considering what happens to an even or odd number of people after the sword goes around the circle once:

J(n) =

• 2*J( (n-1)/2 ) + 1, in the case when n is odd
• 2*J( n/2 ) - 1, in the case when n is even

Use induction on the length L of [n]₂.

The base cases are length L = 1 and 2 in which case one can verify directly the three cases:

• J(1) = 1 is the left_rot of itself
• J(2) = 1 which is the left_rot of 10 = [2]₂
• J(3) = 3 which is the left_rot of 11 = [3]₂

Suppose we know the theorem to be true up to length L. Consider J(n) where n has L+1 bits base 2. Express [n]₂ a the string 1ml where l is the least significant bit, and m is the string consisting of the middle L-1 bits.

Case 1 of the inductive step [n is odd]. So l=1. By the recursive formula for J(n) we have

J(n) = 2*J((n-1)/2)+1

= 2*J( ( number(1m1) - 1) / 2 )+1

= 2*J( number(1m0) / 2 ) + 1

= 2*J( number(1m) ) + 1

= 2*number(m1) + 1

Where in the last step we applied the inductive hypothesis. Continuing on we have

2*number(m1) + 1 = number(m10) + 1

= number(m11)

= rot_left( number(1m1 )

= rot_left( n )

and finishes up the first case.

Case 2 of the inductive step [n is even]. So l=0. By the recursive formula for J(n) we have

J(n) = 2*J(n/2)-1

= 2*J( number(1m0) / 2 ) - 1

= 2*J( number(1m) ) - 1

= 2*number(m1) - 1

Where in the last step we applied the inductive hypothesis. Continuing on we have

2*number(m1) - 1 = number(m10) - 1

= number(m01)

= rot_left( number(1m0 )

= rot_left( n )

and finishes up the second case and the proof in its entirety.