# Josephus problem

See the Josephus Problem. My code takes in two numbers; one is the number of participants, and the other is supposed to be the number of players skipped between executions.

josephus[m_Integer, n_Integer] :=
If[m == 1,
m,
Mod[josephus[m - 1, n] + n - 1, m] + 1]


The problem is that this code actually takes in the number of participants, and the other number n is actually killing the $n^{th}$ player. I don't want that; I want to skip $n$ players. (I.e., I want to kill every $(n+1)^{th}$ player.)

Why is it that replacing n in my code with n+1 does not correct the problem? It gives me totally different values. Since my code works fine if we are killing every $n^{th}$ player, shouldn't I just simply change n to n+1 and the code then kills every $(n+1)^{th}$ player?

Just so it helps, josephus[40,6] should return 24. josephus[40,5] should return 28. Note that currently, josephus[40,7] returns 24 and josephus[40,6] returns 28, which makes sense. The only difference is that, currently, we kill every $n^{th}$ player. I want to kill every $(n+1)^{th}$ player. Why is it that changing n to n+1 doesn't work?

Edit: the output represents the player that survives the game.

• Related: 33595, 64262 Dec 18, 2014 at 14:06

Are you sure you didn't make a mistake? Perhaps you didn't replace both instances of n with n+1?

josephus1[m_Integer, n_Integer] :=
If[m == 1, m, Mod[josephus[m - 1, n + 1] + n, m] + 1]


josephus1[40, 6] returns 24 and josephus1[40, 5] returns 28.

• You replaced n with n+1, but you also defined a new function josephus1 that calls the original josephus. It works but I still don't see why it works this way. Dec 18, 2014 at 15:20
• I see what you're saying; I ended up doing josephus1[m_Integer, n_Integer] := josephus[m, n + 1], I think this form is clearer about "why" it works. I think the recursion as you tried to define just isn't "invariant" in the way you're expecting it to be. I'm sure there's a more intuitive explanation, but I haven't been able to put a finger on it. I'll try to think more carefully about it a bit later.
– Aky
Dec 18, 2014 at 16:02
• I know what you're saying, and I figured that was the problem, but I'm trying to pinpoint the problem in the recursion. Dec 18, 2014 at 16:05

Here is a one-liner

josephus[howmany_Integer?Positive, which_Integer?Positive] :=
Nest[Rest[RotateLeft[#, which]] &, Range[howmany], howmany - 1]


By the way the explicit formula for the problem is given in Knuth book .

• Your solution is equivalent to the one used in method 1 in this question which was already linked in the comment done by @MichaelE2 under the question Dec 18, 2014 at 14:53
• Yes indeed, the problem is too simple :). This is obvious implementation of the section 1.3, where it is considered much more deeply.
– Acus
Dec 18, 2014 at 15:07
• Your solution works well, but keep in mind that I was asking why I can't replace n with n+1 in my existing code. Dec 18, 2014 at 15:22