Josephus problem

1
Josephus problem
In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem
related to a certain counting-out game.
There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and
proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next
person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the
executed people are removed), until only the last person remains, who is given freedom.
The task is to choose the place in the initial circle so that you are the last one remaining and so survive.
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, the exit of which was blocked by
Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves
using a step of three. Josephus states that by luck or possibly by the hand of God, he and another man remained the
last and gave up to the Romans.
The reference comes from Book 3, Chapter 8, par 7 of Josephus' The Jewish War (writing of himself in the third
person):
However, in this extreme distress, he was not destitute of his usual sagacity; but trusting himself to the
providence of God, he put his life into hazard [in the manner following]: "And now," said he, "since it is
resolved among you that you will die, come on, let us commit our mutual deaths to determination by lot. He
whom the lot falls to first, let him be killed by him that hath the second lot, and thus fortune shall make its
progress through us all; nor shall any of us perish by his own right hand, for it would be unfair if, when the rest
are gone, somebody should repent and save himself." This proposal appeared to them to be very just; and
when he had prevailed with them to determine this matter by lots, he drew one of the lots for himself also. He
who had the first lot laid his neck bare to him that had the next, as supposing that the general would die among
them immediately; for they thought death, if Josephus might but die with them, was sweeter than life; yet was
he with another left to the last, whether we must say it happened so by chance, or whether by the providence of
God. And as he was very desirous neither to be condemned by the lot, nor, if he had been left to the last, to
imbrue his right hand in the blood of his countrymen, he persuaded him to trust his fidelity to him, and to live
as well as himself.
[1]
Solution
In the following, denotes the number of people in the initial circle, and denotes the count for each step, that is,
people are skipped and the -th is executed. The people in the circle are numbered from to .
k=2
We explicitly solve the problem when every 2nd person will be killed, i.e. . (For the more general case
, we outline a solution below.) We express the solution recursively. Let denote the position of the
survivor when there are initially people (and ). 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 during the second time around the circle was
originally in position (for every choice of ). Let . The person at who will now survive
Josephus problem
2
was originally in position . 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 was originally in position . This gives us the recurrence
When we tabulate the values of and we see a pattern:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1
This suggests that is an increasing odd sequence that restarts with whenever the index n is a
power of 2. Therefore, if we choose m and l so that and , then . It
is clear that values in the table satisfy this equation. Or we can think that after people are dead there are only
people and we go to the th person. He must be the survivor. So . Below, we give a proof
by induction.
Theorem: If and , then .
Proof: We use strong induction on . The base case is true. We consider separately the cases when is
even and when is odd.
If is even, then choose and such that and . Note that . We
have , where the second equality follows from the
induction hypothesis.
If is odd, then choose and such that and . Note that
. We have , where the second
equality follows from the induction hypothesis. This completes the proof.
We can solve for to get an explicit expression for :
The most elegant form of the answer involves the binary representation of size : can be obtained by a
one-bit left cyclic shift of itself. If we represent in binary as , then the solution is given
by . The proof of this follows from the representation of as or from the above
expression for .
Implementation: A simple python function can be:
def josephus_2( n ):
from math import log
return 2*(n - 2**(int(log(n,2))))+1
The general case
The easiest way to solve this problem in the general case is to use dynamic programming by performing the first step
and then using the solution of the remaining problem. When the index starts from one, then the person at shifts
from the first person is in position , where n is the total number of persons. Let
denote the position of the survivor. After the -th person is killed, we're left with a circle of , and we start
the next count with the person whose number in the original problem was . The position of the
survivor in the remaining circle would be if we start counting at ; shifting this to account for the
fact that we're starting at yields the recurrence
Josephus problem
3
which takes the simpler form
if we number the positions from to instead.
This approach has running time , but for small and large there is another approach. The second
approach also uses dynamic programming but has running time . It is based on considering killing k-th,
2k-th, ..., -th people as one step, then changing the numbering.
Implementation: A simple python function can be (but might be slow/fail for large n and small k):
def josephus(n, k):
if n ==1:
return 1
else:
return ((josephus(n-1,k)+k-1) % n)+1
Alternatively a simple loop can also be run like:
def josephus(n, k):
r = 0
i = 1
while i <= n:
r = (r + k) % i;
i+= 1
return r+1
A dynamic programming solution in Haskell:
josephus n k = josephus' [1..n] k where
josephus' xs k
| length xs == 1 = head xs
| otherwise = josephus' (killnext k xs) k where
killnext k xs = take (length xs - 1) (drop k (cycle xs))
A somewhat more elaborate version in Java:
int josephus(int n, int k) {
return josephus(n, k, 1);
}
int josephus(int n, int k, int startingPoint) {
if(n == 1)
return 1;
int newSp = (startingPoint + k - 2) % n + 1;

int survivor = josephus(n - 1, k, newSp);
if (survivor < newSp) {
return survivor;
} else
return survivor + 1;
}
Josephus problem
4
Variants and generalizations
According to Concrete Mathematics, section 1.3, Josephus had an accomplice; the problem was then to find the
places of the two last remaining survivors (whose conspiracy would ensure their survival).
Extended Josephus problem
Problem definition: There are n persons, numbered 1 to n, around a circle. We eliminate second of every two
remaining persons until one person remains. Given the n, determine the number of xth person who is eliminated.
[2]
Notes
[1] Flavius Josephus, Wars Of The Jews III. 8. 7. (http:/ / www. gutenberg. org/ dirs/ 2/ 8/ 5/ 2850/ 2850-h/ book3. htm#2HCH0008) (Translation
by William Whiston).
[2] Armin Shams-Baragh Formulating The Extended Josephus Problem (http:/ / www. cs. man. ac. uk/ ~shamsbaa/ Josephus. pdf).
References
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). "Chapter 14: Augmenting
Data Structures". Introduction to Algorithms (Second Edition ed.). MIT Press and McGraw-Hill. p.318.
ISBN0-262-03293-7.
External links
Josephus Flavius game (http:/ / www. cut-the-knot. org/ recurrence/ flavius. shtml) (Java Applet) at cut-the-knot
allowing selection of every n
th
out of 50 (maximum).
Josephus Problem at the MathWorld encyclopedia (http:/ / mathworld. wolfram. com/ JosephusProblem. html)
Josephus Problem at Shippensburg University (http:/ / www. maa. org/ publications/ periodicals/ loci/ resources/
the-josephus-problem)
Article Sources and Contributors
5
Article Sources and Contributors
Josephus problem Source: http://en.wikipedia.org/w/index.php?oldid=607954302 Contributors: Adashiel, Amadaeus1010011010, Andre.holzner, Angel ivanov angelov, AnonMoos,
Ashwinkumar b v, Begoon, Bluebusy, Bocianski, Cantons-de-l'Est, Chiok, Courtgoing, Craig Schamp, Crazytales, Crisfilax, Crowborough, Cybercobra, DrHow, Eloy, Favonian, Fuzzyllama,
Giftlite, Gleannnangealt, GregorB, Hairhorn, Hariva, Hebrides, Helopticor, Jitse Niesen, Jogloran, John Shaffer, Joriki, KOTEHOK, Lantonov, LcawteHuggle, LutherVinci, MDMCP,
Markunit23, Masterzora, Matthias Kupfer, Maxal, Me nishant, Michael Hardy, Mooncow, Mormegil, Napx, Niskand, PL290, PV=nRT, Phil Boswell, Philip Trueman, Poliocretes, Ptrillian,
Rachelskit, Radagast83, RobinK, Robinh, Sintau.tayua, Sycthos, Toddst1, Tow, Trovatore, Ty683g542, Vikas.veshishth, Wasell, Yelnatz, 94 anonymous edits
License
Creative Commons Attribution-Share Alike 3.0
//creativecommons.org/licenses/by-sa/3.0/