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 by the size of the group. The recursion can be written as follows:

can represented in binary as: , i.e where and the remaining are 0 or 1.

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

- yields

Therefore,

Repeating this till ,

N0w, note if then hence and implies .

Therefore,

Using the notation of the wikipedia entry and the definition above,

Now it follows:

- yields
- yields , i.e cyclic left shift of one

The latter can be seen as follows:

as

**Notes:**

WordPress posed problems in arrays in this post. I apologise for the less than ideal formatting.

Advertisements

Categories: Mathematics

Comments (0)
Trackbacks (0)
Leave a comment
Trackback