Josephus' Problem

Algorithm description

This algorithm is named for a historian of the first century, Flavius Josephus, who survived the Jewish-Roman war due to his mathematical talents. Legend has it that he was one out of 41 Jewish rebels trapped by the Romans. His companions preferred suicide to escape, so they decided to form a cycle and to kill every third person and to proceed around the circle until no one was left. Josephus wasn't excited by the idea of killing himself, so he calculated where he has to stand to survive the vicious circle. The following implementation demands the input of how many people will stand around a circle and how many shall be passed over before the next one is killed.

Algorithm implementation:

 1  function josephus (N: positive; m: positive) return positive
 2  is
 3      x : positive;
 4      a : double;
 5  begin
 6      a := double(m);
 7      discrete d := 1 in 1..((m-1)*N) 
 8          new d := ceiling((a/(a-1.0))*double(d))
 9      loop
10          d := ceiling((a/(a-1.0))*double(d));
11          x := d;
12      end loop;
13      return m*N+1-x;
14  end josephus;

[ Sourcefile ]

Notes on design

This implementation is based upon the following train of thought: whenever a person is passed over, we can assign a new number, e.g. say every third person is passed over, then 1 and 2 become n+1 and n+2, 3 is killed, 4 becomes n+3 and so on. Now it can be shown that this renumbering ends with qn, where n is the number of persons and every qth person is eliminated. Now we can use qn to figure out who the survivor is. We use the following algorithm (Jq(n) denotes the survivor):
D := 1;
while D<=(q-1)n do D:=ceiling(D*q/(q-1));
Jq(n) := qn+1-D;
 In our implementation the while-construct was replaced by a discrete-loop.

Worst Case Performance

Let's begin with a look at our recurrent definition:
D0=1
Dn=ceiling(D*q/(q-1)) until D>(q-1)n
We want to find out the number of iterations in the worst case, so let's assume we drop the ceiling-function. Now every new calculated value of D is a real number instead of an integer number, which is lower than or in some cases equal to the integer number. In this case we can substitute the above definition by the following simplified definition:
Di=(q/(q-1))i with i>=0
With (q-1)n as our upper bound, the loop is executed until
(q/(q-1))i > (q-1)n or:
the number of iterations in the worst case is limited to:

log(qn-n)/log(q/(q-1))

Selected Bibliography

[GKP89, p. 79]

[ Samples Overview | Bibliography | WOOP Project ]