# A Recursive Formula For Generalized Josephus problem

The Josephus Problem asks where to start taking out every kth person in the circle consisted of n people, such that you are the last "survivor".

The following recursive formula is given: \begin{align} f(1,k)&=1, \\ f(n,k)&=((f(n-1,k)+k-1) \bmod n )+1. \end{align}

But this is not enough explanation, so I don't get where does it come from.

Can anyone help?

-
You mean wiki explanation in general case is not enough? –  user742 Nov 30 '12 at 17:43

Let me explain the idea. Assume that indices start from 0. Take N = 6 and K = 3 So initial arrangement looks something like

0->1->2->3->4->5->0.... like a circle.

After round 1 , '2' is eliminated .

0->1->2->3->4->5->0->1...

....(k)->0->1->2->3->

here (k) denotes the person is killed

Since we ought to start from the last position we killed, so lets look at the updated indices.

Old Index | New Index

3 | 0

4 | 1

5 | 2

and so on.... looking closely we can easily see after each round

OldPosition = (newPosition+k)mod N

Where N is the number of people left before the round started.

Also OldPosition signifies f(N,K)

and New Position signifies f(N-1,K) as one person has already been killed.

So putting it back to OldPostion = (newPostion+k) mod N we get

f(N,K) = ( f(N-1,K)+ K ) mod N

But this is done only if u have indices starting from 0. If u want to rearrange for indices starting from 1, you can rearrange it to get the above result.

I found a beautiful paper on this