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.
In the particular counting-out game that gives rise to the Josephus problem, a number of 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.
The problem is named after Flavius Josephus, a Jewish historian and leader who lived in the 1st century. According to Josephus's firsthand 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's 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.
As to intentionality, Josephus asked: “shall we put it down to divine providence or just to luck?”[1] 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”.[2] 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).
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 .
In the following,
n
k
k-1
k
1
n
1
The problem is explicitly solved when every second person will be killed (every person kills the person on their left or right), i.e.
k=2
k ≠ 2
f(n)
k=2
If the initial number of people were even, then the person in position during the second time around the circle was originally in position
2x-1
n=2j
f(j)
2f(j)-1
f(2j)=2f(j)-1 .
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
2x+1
f(2j+1)=2f(j)+1 .
When the values are tabulated of
n
f(n)
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ||
f(n) | 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
This suggests that
f(n)
f(n)=1
n=2m+l
0\leql<2m
f(n)=2l+1
2m
2l+1
f(n)=2l+1
Theorem: If
n=2m+l
0\leql<2m
f(n)=2l+1
Proof: The strong induction is used on . The base case
n=1
If is even, then choose
l1
m1
n/2=
m1 | |
2 |
+l1
0\leql1<
m1 | |
2 |
l1=l/2
f(n)=2f(n/2)-1=2((2l1)+1)-1=2l+1
If is odd, then choose
l1
m1
(n-1)/2=
m1 | |
2 |
+l1
0\leql1<
m1 | |
2 |
l1=(l-1)/2
f(n)=2f((n-1)/2)+1=2((2l1)+1)+1=2l+1
can be solved to get an explicit expression for
f(n)
f(n)=
\lfloorlog2(n)\rfloor | |
2(n-2 |
)+1
The most elegant form of the answer involves the binary representation of size :
f(n)
n=1b1b2b3...bm
f(n)=b1b2b3...bm1
2m+l
f(n)
Implementation: If denotes the number of people, the safe position is given by the function
f(n)=2l+1
n=2m+l
0\leql<2m
Now if the number is represented in binary format, the first bit denotes
2m
n = 1 0 1 0 0 1 2m = 1 0 0 0 0 0 l = 0 1 0 0 1
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. Input must be a positive integer.
n = 1 0 1 0 0 1 n = 0 1 0 0 1 1
In 1997, Lorenz Halbeisen and Norbert Hungerbühler discovered a closed-form for the case
k=3
\alpha ≈ 0.8111...
that can be computed to arbitrary precision. Given this constant, choose to be the greatest integer such that
\operatorname{round}(\alpha ⋅ (3/2)m)\len
m\prime=\operatorname{round}(log3/2n/\alpha)
m\prime-1
f(n)=3(n-\operatorname{round}(\alpha ⋅ (3/2)m))+(2
1)
for all
n\ge5
As an example computation, Halbeisen and Hungerbühler give
n=41,k=3
m\prime ≈ \operatorname{round}(log3/241/0.8111) ≈ \operatorname{round}(9.68)=10
\operatorname{round}(\alpha ⋅
m\prime | |
(3/2) |
) ≈ \operatorname{round}(0.8111 ⋅ (3/2)10)=47
m=9
\operatorname{round}(0.8111 ⋅ (3/2)9) ≈ \operatorname{round}(31.18)=31
f(n)=3(41-31)+1=31
This can be verified by looking at each successive pass on the numbers through :
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
s
((s-1)\bmodn)+1
f(n,k)
k
n-1
(k\bmodn)+1
f(n-1,k)
1
(k\bmodn)+1
f(n,k)=((f(n-1,k)+k-1)\bmodn)+1,withf(1,k)=1,
which takes the simpler form
g(n,k)=(g(n-1,k)+k)\bmodn,withg(1,k)=0
if the positions are numbered from
0
n-1
O(n)
k
n
O(klogn)
(\lfloorn/k\rfloork)
This improved approach takes the form
g(n,k)=\begin{cases} 0&ifn=1\\ (g(n-1,k)+k)\bmodn&if1<n<k\\ \begin{Bmatrix} g(n-\left\lfloor
n | |
k |
\right\rfloor,k)-n\bmodk+n&ifg(n-\left\lfloor
n | |
k |
\right\rfloor,k)<n\bmodk\\ \lfloor
| ||||||
k-1 |
\rfloor&ifg(n-\left\lfloor
n | |
k |
\right\rfloor,k)\gen\bmodk \end{Bmatrix}&ifk\len\\ \end{cases}