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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Dec 18, 2014 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
    Commented Dec 18, 2014 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
    Commented Dec 18, 2014 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 .

Improve this answer
$\endgroup$
3
  • 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
    Commented Dec 18, 2014 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$
    – Acus
    Commented Dec 18, 2014 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
    Commented Dec 18, 2014 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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