1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Sultan of Swing Dec 18 '14 at 15:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Aky Dec 18 '14 at 16:02
  • $\begingroup$ I know what you're saying, and I figured that was the problem, but I'm trying to pinpoint the problem in the recursion. $\endgroup$ – Sultan of Swing Dec 18 '14 at 16:05
1
$\begingroup$

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 .

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Dr. belisarius Dec 18 '14 at 14:53
  • $\begingroup$ Yes indeed, the problem is too simple :). This is obvious implementation of the section 1.3, where it is considered much more deeply. $\endgroup$ – user18792 Dec 18 '14 at 15:07
  • $\begingroup$ 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. $\endgroup$ – Sultan of Swing Dec 18 '14 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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