Josephus Problem

Flavius Josephus was a famous historian of the first century. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and to kill every third remaining person until no one was left. But Josephus, along with an unindicted conspirator, wanted none of this suicide nonsense and therefore quickly calculated where he and his friend should stand in the circle so that they can survive.

We will start with \(n\) people numbered \(1\) to \(n\) around a circle, and we'll eliminate every second remaining person until only one survives (the main problem is to find the survivor's number).

Let \(J(n)\) be the survivor's number, and as an example take \(n=10\), then the order of elimination would be 2,4,6,8,10,3,7,9,1. So, number 5 survives. Therefore, \(J(10)=5\).

It is easy to notice that \(J(n)\) is always an odd number because the first trip around the circle would eliminate all the even numbers. Also, if \(n\) is even number then we will come at the same situation except this time there are only half as many people and their numbers have changed.

Now let us take another case in which \(n=2^k\) for some positive integral value of \(k\). In this case the person with number \(1\) survives in the last always or \(J(n)=1\).

Now if we take a value \(n\) which may not be equal to a perfect power of \(2\), then

\[n=m+2^k,\]

where \(2^k \leq n\) and \(m\) is a non-negative integer.

Now we just need to count till \(m\) number of people are executed and then next person will be the one who will survive the deadly procedure.

Also, notice that if you want to find the number of person who was executed \(2^{nd}\) in the process, the number is \(4\); if you want to find the number of person who was executed \(3^{rd}\) in the process, the number is \(6\), and so on. In general the person executed \(m^{th}\) in the process has number is \(2m\). (Note that this generalization is only valid when \(m < n\), in our case its true as \(m=n-2^k\).)

The person standing next with number \(2m\) will have number \(2m+1\).

\[\begin{align} J(n) &= 2m+1\\ &= 2(n-2^k)+1\\ &= 2n-2^{k+1}+1, \end{align}\]

where \(2^k \leq n.\).