Home > Mathematics > Two Step Josephus

## Two Step Josephus

In this post, I aim to approach the solution for the  Josephus problem for  (n,2) constructively. The motivation is amplification of the  wikipedia entry.

The Josephus problem for step size 2 (i.e. killing of alternate members of group), allows recursive definition of the position of the last person (see the wikipedia entry). Let $n$ by the size of the group.  The recursion can be written as follows:

$f(n)= 2 f(\lfloor{\frac{n}{2}\rfloor}) + (-1)^{n+1}$

$n$ can represented in binary as: $b_0b_1\ldots b_m$ , i.e $n = \sum_{j=0}^m b_{m-j}2^j$ where $b_0 =1$ and the remaining $b_{1\leq j\leq m}$ are 0  or 1.

Now I make the following observations (excuse some notational abuses):

• $\lfloor {\frac{n}{2}}\rfloor = \lfloor{b_0\ldots b_m/10}\rfloor = b_0\ldots b_{m-1}$
• $n = 2^m + l$ yields $l=b_1\ldots b_m$
• $\sum_{j=0}^{m-1} 2^j =2^m -1$
• $b_0 =1, f(b_0) =1$
Therefore,
$f(b_0\ldots b_m) = 2 f(b_0\ldots b_{m-1}) + (-1)^{b_m+1}$
Repeating this till $f(b_0)$,
$f(b_0\ldots b_m) = 2^m f(b_0) + \sum_{j=0}^{m-1} (-1)^{b_{m-j}+1}2^j$
$f(b_0\ldots b_m) =(2^m -1 +\sum_{j=0}^{m-1} (-1)^{b_{m-j}+1} 2^j )+1$
$f(b_0\ldots b_m)=\sum_{j=0}^{m-1} (1+(-1)^{b_{m-j}+1})2^j +1$
N0w, note if $b_j =0$ then $(-1)^{b_j +1}=-1$ hence $1+ (-1)^{b_j+1}=0=2^{m-j}\times 0=2 b_j$ and $b_j =1$ implies $1 +(-1)^{b_j+1}=2=2 b_j$.
Therefore,
$f(b_0\ldots b_m) = \sum_{j=0}^{m-1} 2 b_{m-j}2^j \quad +1$
$f(b_0\ldots b_m)= 2\sum_{j=0}^{m-1} b_{m-j}2^j\quad +1 =10 \times b_1\ldots b_m +1$
Using the notation of the wikipedia entry and the definition above,
$f(n) = 2 l +1$
Now it follows:
• $n =2^k$ yields $f( 10\ldots 0)= 1$
• $n=b_0\ldots b_m$ yields $f(b_0\ldots b_m) = b_1b_2\ldots b_mb_0$ , i.e cyclic left shift of one
The latter can be seen as follows:
$2l +1 =2n -2^{m+1} +1$
$2n =b_0\ldots b_m0$
$2n-2^{m+1} = b_1\ldots b_m0$ as $b_0 =1$
$2n-2^{m+1} +1 =b_1\ldots b_m1=b_1\ldots b_mb_0$
Notes:
WordPress posed problems in $\LaTeX$ arrays in this post. I apologise for the less than ideal formatting.