Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|cite|improve this question
You mean wiki explanation in general case is not enough? – user742 Nov 30 '12 at 17:43

1 Answer 1

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 .



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

Hope this helps :)

share|cite|improve this answer
Welcome to Computer Science! We aim to be a source of information, rather than just a link farm so it would be great if you could at least summarize the contents of the paper and explain how it answers the question. – David Richerby Jun 20 at 19:52
thanks @DavidRicherby , i have updated my answer on this. – Sukhmeet Singh Jun 21 at 8:10
Thanks! That's great. – David Richerby Jun 21 at 9:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.