Josephus problem

The Josephus problem or the Josephus permutation is a theoretical problem from computer science or mathematics .

There are arranged numbered objects in the circuit; then, starting with the number , every th object is removed, the circle being closed again and again. The order of the removed objects is called the Josephus permutation. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$

The aim of this problem is to determine the last object of the permutation given and . ${\displaystyle n}$ ${\displaystyle k}$

history

The problem was named after the Jewish historian Flavius ​​Josephus , who hid from the Romans in a cave with 40 other men during the battle for the Galilean city ​​of Jotapata in AD 67 . When the hiding place was betrayed, the Romans assured Josephus of safe conduct in case he left the hiding place. His followers, however, threatened to kill him and would rather die than fall into the hands of the Romans. Thereupon Josephus made the proposal of a collective suicide , in which everyone should line up in a circle and every third person should be killed by his right neighbor. He placed himself in 16th place, remaining second to last and overpowered the weaker man in 31st place. Both surrendered to the Romans and survived.

solution

The problem is solved here in the event that every 2nd element is removed ( ). For the general case , a solution follows below. The solution is derived using recursion. denote the last element of the permutation, if elements were present at the beginning (with ). In the first pass, all even-numbered elements are removed. In the second round, the elements that are in the new 2nd, 4th etc. position are removed, as if there had been no first round. If the starting number of elements is even, then the element from the second round was in position in the first round . The element was originally in position . This results in the following recursion formula: ${\displaystyle k=2}$ ${\displaystyle k\neq 2}$ ${\displaystyle f(n)}$ ${\displaystyle n}$ ${\displaystyle k=2}$ ${\displaystyle x}$ ${\displaystyle 2x-1}$ ${\displaystyle f(2n)}$ ${\displaystyle 2f(n)-1}$

${\displaystyle f(2n)=2f(n)-1.\,}$

If the number of elements is odd at the beginning, then the original first element is removed in the second round, but here too the new 2nd, 4th etc. element is removed. In this case it turns out that Element was in position on the first lap . From this follows the recursion formula: ${\displaystyle x}$ ${\displaystyle 2x+1}$

${\displaystyle f(2n+1)=2f(n)+1.\,}$

If you display the values ​​for and in a table, you can see a pattern: ${\displaystyle n}$ ${\displaystyle f(n)}$

${\displaystyle n}$	1	2	3	4th	5	6th	7th	8th	9	10	11	12	13	14th	15th	16
${\displaystyle f(n)}$	1	1	3	1	3	5	7th	1	3	5	7th	9	11	13	15th	1

This table suggests that there is an ascending sequence of odd numbers that starts again when the index is a power of two. If one chooses and so that and then follows . It is obvious that the values ​​from the table satisfy this equation. Proof is given below by complete induction . ${\displaystyle f(n)}$ ${\displaystyle f(n)=1}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle l}$ ${\displaystyle n=2^{m}+l}$ ${\displaystyle 0\leq l<2^{m}}$ ${\displaystyle f(n)=2\cdot l+1}$

Assertion: If and , then follows . ${\displaystyle n=2^{m}+l}$ ${\displaystyle 0\leq l<2^{m}}$ ${\displaystyle f(n)=2l+1}$

Proof: Complete induction over . The case is true. Consider the cases for even and odd separately. ${\displaystyle n}$ ${\displaystyle n=1}$ ${\displaystyle n}$ ${\displaystyle n}$

If straight, then choose and so, that and . It applies . We have where the second equation follows from the induction hypothesis. ${\displaystyle n}$ ${\displaystyle l_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle n/2=2^{m_{1}}+l_{1}}$ ${\displaystyle 0\leq l_{1}<2^{m_{1}}}$ ${\displaystyle l_{1}=l/2}$ ${\displaystyle f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1}$

If odd, then choose one and such that and . It applies . We have where the second equation also follows from the induction hypothesis. Therefore the statement is proven. ${\displaystyle n}$ ${\displaystyle l_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$ ${\displaystyle 0\leq l_{1}<2^{m_{1}}}$ ${\displaystyle l_{1}=(l-1)/2}$ ${\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1}$

The most elegant form of the solution follows from the binary representation of : can be determined by itself by a 1-bit left rotation . If one is represented in binary as , then the solution is given as . The proof follows from the representation of as . ${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n=b_{0}b_{1}b_{2}b_{3}\dots b_{m}}$ ${\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}}$ ${\displaystyle n}$ ${\displaystyle 2^{m}+l}$

The dynamic programming is the easiest way to solve this problem for the general case.

This method uses the recursion formula:

${\displaystyle f(n,k)=(f(n-1,k)+k-1){\bmod {n}}}$, With ${\displaystyle f(1,k)=0}$

which is obvious when you consider how the number of the last item changes when you go from to . This method has a running time of , but there is a different approach for both small and large . This second approach also uses dynamic programming, but only requires a runtime of . He removes the k ., 2 k ., ..., . Items in one step and then changes the numbering. ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(k\log n)}$ ${\displaystyle \lfloor n/k\rfloor }$

implementation

The following algorithm realizes the problem recursively according to the above recursion formula for the case k = 2 and has a running time of O (log (n)) .

int josephus(int n) 
{
    if(n == 1) 
        return 1;

    if((n%2) == 0) 
        return 2 * josephus(n / 2) - 1;

    if((n%2) == 1) 
        return 2 * josephus((n - 1) / 2) + 1;
}

According to the closed formula f (n) = 2 * l + 1 , the following non-recursive algorithm can be specified. Its running time is in O (1) .

int josephus(int n)
{
    m = floor( log2(n) );
    l = n - 2^m;
    j = 2*l + 1;

    return j;
}

literature

• Paul Yiu : Recreational Mathematics , Florida Atlantic University: Department of Mathematics (available as PDF in English; 868 kB)
• Walter William Rouse Ball , Harold Scott Macdonald Coxeter : Mathematical Recreations and Essays , Dover, 1987. Pages 32-36, ISBN 0-486-25357-0
• Ronald L. Graham , Donald E. Knuth, and Oren Patashnik : Concrete Mathematics: A Foundation for Computer Science , Massachusetts, 1994. Pages 8-16, ISBN 978-0-201-55802-9