thumb|upright=1.3|[[Claude Gaspar Bachet de Méziriac's interpretation of the Josephus problem with 41 soldiers and a step size of 3, showing that places 16 and 31 are last to be killed – time progresses inwards along the spiral, green dots denoting live soldiers, grey dead soldiers, and crosses killings]]

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. Such games are used to pick out a person from a group, e.g. eeny, meeny, miny, moe.

[[File:JosephusProblemDrawing.png|thumb|right|A drawing for the Josephus problem sequence for 500 people and skipping value of 6. The horizontal axis is the number of the person. The vertical axis (top to bottom) is time (the number of cycle). A live person is drawn as green, a dead one is drawn as black. But the surviving Slavonic manuscript of Josephus tells a different story: that he “counted the numbers cunningly and so managed to deceive all the others”. 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

thumb|Variant of the Josephus problem with 30 people and a step size of 9 – time progresses inwards along the spiral, green dots denoting live soldiers, grey dead soldiers, and crosses killings

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. The Christians need to determine where to stand to ensure that only the Turks are tossed. In other versions the roles of Turks and Christians are interchanged.

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. It is supposed 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

[[File:Josephus_problem_table.svg|thumb|link=|Penultimate (pink) and ultimate (ultramarine) places in the Josephus problem for various group size, n and step size, k. In [ the SVG file,] hover over the values to show the full order of killing.]]

In the following, <math>n</math> denotes the number of people in the initial circle, and <math>k</math> denotes the count for each step, that is, <math>k-1</math> people are skipped and the <math>k</math>-th is executed. The people in the circle are numbered from <math>1</math> to <math>n</math>, the starting position being <math>1</math> and the counting being inclusive.

k = 2

The problem is explicitly solved when every second person will be killed (every person kills the person on their left or right), i.e. <math>k = 2</math>. (For the more general case <math>k \neq 2</math>, a solution is outlined below.)

The solution is expressed recursively. Let <math>f(n)</math> denote the position of the survivor when there are initially people (and <math>k = 2</math>).

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 is as though there were no first time around the circle.

If the initial number of people were even, then the person in position during the second time around the circle was originally in position <math>2x - 1</math> (for every choice of ). Let <math>n = 2j</math>. The person at <math>f(j)</math> who will now survive was originally in position <math>2f(j) - 1</math>. This yields the recurrence

<math display="block">

f(2j) = 2f(j) - 1.

</math>

If the initial number of people were odd, then person 1 can be thought of 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 was originally in position <math>2x + 1</math>. This yields the recurrence

<math display="block">

f(2j + 1) = 2f(j) + 1.

</math>

When the values are tabulated of <math>n</math> and <math>f(n)</math> a pattern emerges (, also the leftmost column of blue numbers in the figure above):

{| class="wikitable" style="text-align: center;"

!

| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16

|-

!<math>f(n)</math>

| 1 || 1 || 3 || 1 || 3 || 5 || 7 || 1 || 3 || 5 || 7 || 9 || 11 || 13 || 15 || 1

|}

This suggests that <math>f(n)</math> is an increasing odd sequence that restarts with <math>f(n) = 1</math> whenever the index n is a power of 2.

Therefore, if m and are chosen so that <math>n = 2^m + l</math> and <math>0 \leq l < 2^m</math>, then <math>f(n) = 2l + 1</math>.

It is clear that values in the table satisfy this equation. Or it can be thought that after people are dead, there are only <math>2^m</math> people, and it goes to the <math>2l + 1</math>st person. This person must be the survivor. So <math>f(n) = 2l + 1</math>. Below, a proof is given by induction.

Theorem: If <math>n = 2^m + l</math> and <math>0 \leq l < 2^m</math>, then <math>f(n) = 2l + 1</math>.

Proof: The strong induction is used on . The base case <math>n=1</math> is true.

The cases are considered separately when is even and when is odd.

If is even, then choose <math>l_1</math> and <math>m_1</math> such that <math>n/2 = 2^{m_1} + l_1</math> and <math>0 \leq l_1 < 2^{m_1}</math>. Note that <math>l_1 = l/2</math>. <math>f(n) = 2f(n/2) - 1 = 2[(2l_1) + 1] - 1 = 2l + 1</math> is had where the second equality follows from the induction hypothesis.

If is odd, then choose <math>l_1</math> and <math>m_1</math> such that <math>(n - 1)/2 = 2^{m_1} + l_1</math> and <math>0 \leq l_1 < 2^{m_1}</math>. Note that <math>l_1 = (l - 1)/2</math>. <math>f(n) = 2f[(n - 1)/2] + 1 = 2[(2l_1) + 1] + 1 = 2l + 1</math> is had where the second equality follows from the induction hypothesis. This completes the proof.

can be solved to get an explicit expression for <math>f(n)</math>:

<math display="block">

f(n) = 2(n - 2^{\lfloor \log_2(n) \rfloor}) + 1.

</math>

The most elegant form of the answer involves the binary representation of size : <math>f(n)</math> can be obtained by a one-bit left cyclic shift of itself. If is represented in binary as <math>n = 1 b_1 b_2 b_3\dots b_m</math>, then the solution is given by <math>f(n) = b_1 b_2 b_3 \dots b_m 1</math>. The proof of this follows from the representation of as <math>2^m + l</math> or from the above expression for <math>f(n)</math>.

Implementation: If denotes the number of people, the safe position is given by the function <math>f(n) = 2l + 1</math>, where <math>n = 2^m + l</math> and <math>0 \leq l < 2^m</math>.

Now if the number is represented in binary format, the first bit denotes <math>2^m</math> and remaining bits will denote . For example, when , its binary representation is

n = 1 0 1 0 0 1

2<sup>m</sup> = 1 0 0 0 0 0

l = 0 1 0 0 1

<syntaxhighlight lang="java">

/**

  • @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);

return 2 * valueOfL + 1;

}

</syntaxhighlight>

Bitwise

The easiest way to find the safe position is by using bitwise operators. In this approach, shifting the most-significant set bit of to the least significant bit will return the safe position.

</references>

Sources

Further reading

  • FUN2010
  • Josephus Flavius game (Java Applet) at cut-the-knot allowing selection of every n<sup>th</sup> out of 50 (maximum).
  • Generalized Josephus Problem