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?

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

http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf

Hope this helps :)

StackExchange Computer Science Q#7048, answer score: 4