Josephus problem

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.
People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.
The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution.
History.
The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave by Roman soldiers. They chose suicide over capture, and settled on a serial method of committing suicide by drawing lots. Josephus states that by luck or possibly by the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves. This is the story given in Book 3, Chapter 8, part 7 of Josephus' "The Jewish War" (writing of himself in the third person):
The details of the mechanism used in this feat are rather vague. According to James Dowdy and Michael Mays, in 1612 Claude Gaspard Bachet de Méziriac suggested the specific mechanism of arranging the men in a circle and counting by threes to determine the order of elimination. This story has been often repeated and the specific details vary considerably from source to source. For instance, Israel Nathan Herstein and Irving Kaplansky (1974) have Josephus and 39 comrades stand in a circle with every seventh man eliminated. A history of the problem can be found in S. L. Zabell's "Letter to the editor" of the "Fibonacci Quarterly".
Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival). It is alleged that he placed himself and the other man in the 31st and 16th place respectively (for = 3 below).
Variants and generalizations.
A medieval version of the Josephus problem involves 15 Turks and 15 Christians aboard a ship in a storm which will sink unless half the passengers are thrown overboard. All 30 stand in a circle and every ninth person is to be tossed into the sea. Where should the Christians stand to ensure that only the Turks are tossed? In other versions the roles of Turks and Christians are interchanged.
In "Concrete Mathematics: A Foundation for Computer Science", Graham, Knuth and Patashnik describe and study a "standard" variant: Determine where the last survivor stands if there are people to start and every second person ( = 2 below) is eliminated.
A generalization of this problem is as follows. We suppose that every th person will be executed from a group of size , in which the th person is the survivor. If there is an addition of people to the circle, then the survivor is in the -th position if this is less than or equal to . If is the smallest value for which , then the survivor is in position .
Solution.
In the following, formula_1 denotes the number of people in the initial circle, and formula_2 denotes the count for each step, that is, formula_3 people are skipped and the formula_2-th is executed. The people in the circle are numbered from formula_5 to formula_1, the starting position being formula_5 and the counting being inclusive.
k=2.
We explicitly solve the problem when every second person will be killed, i.e. formula_8. (For the more general case formula_9, we outline a solution below.)
We express the solution recursively. Let formula_10 denote the position of the survivor when there are initially formula_1 people (and formula_8).
The first time around the circle, all of the even-numbered people die.
The second time around the circle, the new 2nd person dies, then the new 4th person, etc.; it's as though there were no first time around the circle.
If the initial number of people was even, then the person in position formula_13 during the second time around the circle was originally in position formula_14 (for every choice of formula_13). Let formula_16. The person at formula_17 who will now survive was originally in position formula_18. This gives us the recurrence
If the initial number of people was odd, then we think of person 1 as dying at the end of the first time around the circle. Again, during the second time around the circle, the new 2nd person dies, then the new 4th person, etc.
In this case, the person in position formula_13 was originally in position formula_21. This gives us the recurrence
When we tabulate the values of formula_1 and formula_10 we see a pattern: 
This suggests that formula_10 is an increasing odd sequence that restarts with formula_26 whenever the index "n" is a power of 2.
Therefore, if we choose "m" and "l" so that formula_27 and formula_28, then formula_29.
It is clear that values in the table satisfy this equation. Or we can think that after formula_30 people are dead there are only formula_31 people and we go to the formula_32th person. He must be the survivor. So formula_33. Below, we give a proof by induction.
Theorem: If formula_27 and formula_28, then formula_36.
Proof: We use strong induction on formula_1. The base case formula_38 is true.
We consider separately the cases when formula_1 is even and when formula_1 is odd.
If formula_1 is even, then choose formula_42 and formula_43 such that formula_44 and formula_45. Note that formula_46.
We have formula_47, where the second equality follows from the induction hypothesis.
If formula_1 is odd, then choose formula_42 and formula_43 such that formula_51 and formula_45. Note that formula_53.
We have formula_54, where the second equality follows from the induction hypothesis. This completes the proof.
We can solve for formula_30 to get an explicit expression for formula_10:
The most elegant form of the answer involves the binary representation of size formula_1: formula_10 can be obtained by a one-bit left cyclic shift of formula_1 itself. If we represent formula_1 in binary as formula_62, then the solution is given by formula_63. The proof of this follows from the representation of formula_1 as formula_65 or from the above expression for formula_10.
Implementation: If n denotes the number of people, the safe position is given by the function formula_36 ,where formula_27 and formula_28.
Now if we represent the number in binary format, the first bit denotes formula_31 and remaining bits will denote formula_30. For example, when n=41, its binary representation is
n = 1 0 1 0 0 1
2m = 1 0 0 0 0 0
l = 0 1 0 0 1
 * 
 * @param n the number of people standing in the circle
 * @return the safe position who will survive the execution 
 * f(N) = 2L + 1 where N =2^M + L and 0 <= L < 2^M
 public int getSafePosition(int n) {
 // find value of L for the equation
 int valueOfL = n - Integer.highestOneBit(n);
 int safePosition = 2 * valueOfL + 1;
 return safePosition;
Bitwise.
The easiest way to find the safe position is by using bitwise operators. In this approach, shifting the most-significant set bit of n to the least significant bit will return the safe position. Input must be a positive integer.
n = 1 0 1 0 0 1
n = 0 1 0 0 1 1
 * 
 * @param n (41) the number of people standing in the circle
 * @return the safe position who will survive the execution 
 * ~Integer.highestOneBit(n*2)
 * Multiply n by 2, get the first set bit and take its complement
 * ((n«1) | 1)
 * Left Shift n and flipping the last bit
 * ~Integer.highestOneBit(n*2) & ((n«1) | 1) 
 * Bitwise And to copy bits exists in both operands.
 public int getSafePosition(int n) {
 return ~Integer.highestOneBit(n*2) & ((n«1) | 1);
k=3.
In 1997, Lorenz Halbeisen and Norbert Hungerbühler discovered a closed-form for the case formula_72. They showed that there is a certain constant
that can be computed to arbitrary precision. Given this constant, choose formula_74 to be the greatest integer such that formula_75 (this will be either formula_76 or formula_77). Then, the final survivor is
for all formula_80.
As an example computation, Halbeisen and Hungerbühler give formula_81 (which is actually the original formulation of Josephus' problem). They compute:
We can verify this looking at each successive pass on the numbers formula_5 through formula_88:
The general case.
Dynamic programming is used to solve this problem in the general case by performing the first step and then using the solution of the remaining problem. When the index starts from one, then the person at formula_97 shifts from the first person is in position formula_98, where n is the total number of persons. Let formula_99 denote the position of the survivor. After the formula_2-th person is killed, we're left with a circle of formula_101, and we start the next count with the person whose number in the original problem was formula_102. The position of the survivor in the remaining circle would be formula_103 if we start counting at formula_5; shifting this to account for the fact that we're starting at formula_102 yields the recurrence
which takes the simpler form
if we number the positions from formula_108 to formula_101 instead.
This approach has running time formula_110, but for small formula_2 and large formula_1 there is another approach. The second approach also uses dynamic programming but has running time formula_113. It is based on considering killing "k"-th, 2"k"-th, ..., formula_114-th people as one step, then changing the numbering.
This improved approach takes the form