Dear Sir:

I was so happy to find this site. It's really cool, and I really needed the algorithm for m=2 in the Josephus recursion problem.

It states that you are addressing m=2 in the simple solution, and the graphics appear to support this, but the data and the algorithm support m=1. I'm a little confused.

Am I correct?

I apologize if not.

Katherine

> graphics appear to support this, but
> the data and the algorithm support m=1.
> I'm a little confused.

No, no. It's I who is confused. In what way the data and the algorithm support m=1?

Dear Sir:

Thank you for responding.

If I play the game by hand (as my teacher explained it):

m=1:
pass ball from 1 to 2, two is out, 3 picks up and passed to 4, 4 is out.

series of winners for n= 1 to 10 is: 1 1 3 1 3 5 7 1 3 5 ...

ex: in a 2 player game, pass ball from 1 to 2. 2 is out so 1 wins.

m=2
pass ball from 1 to 2 who passes to 3, 3 is out, 4 picks up and passes to 5

series of winners for n= 1 to 10 is: 1 2 2 1 4 1 4 7 1 4

ex: in a 2 player game, pass ball from 1 to 2 to 1. 1 is out, 2 wins.

I also coded Weis's algorithm using datastructures for m=1 and m=2 and they matched these numbers. But I'm looking for a recursive algorithm for m=2.

I thought your partial recursive solution of the Josephus problem stated it was using m=2, but the data used in the example supports m=1. I implemented the algorithm and got m=1 data.

Look forward to your response again.

Thanks
katherine

Well, it's a matter of terminology - I never talked to your teacher. In my notations you count this way

m=2:

1 2 (out) 3 4 (out) ...

m=3:

1 2 3 (out) ...

My m is 1 more than yours.

I am pretty sure no one has a recursive solution for m = 2 in your notations. You may try another solution on my page that does not produce a formula but leads to an answer.

Regards,
Alexander Bogomolny

So in your notation you don't have an m=0. Which in my book says if m=0, then players are eliminated in order and the last player always wins. That would be your m=1?

We're using: Data Structures and Problem Solving using JAVA by Mark Allen Weiss. In Chapter 13 is the Josephus problem (pg 349). I heard the C++ book he wrote had the same problems. Problem 13.6 gives an algorithm for M=1 (but I like yours better, but you call it M=2). Yours and his yield the same results.

13.8 asks for the general formula for an N player game with m=2. He calls m - passes. I assumed it was recursive, but maybe not.

Anyway, thanks.

katherine

Dear Sir:

Here is a recursive algorithm J(n) I came up with for my m=2 notation (your m=3):

n = number of players
J(n-1) = previous player's winner (the recursive call to this algorithm)
w = winner

if (n=0) then w = 0 else
if (n=1) then w = 1 else
if (J(n-1)==n-1) then w = 2 else
if (J(n-1)==n-2) then w = 1 else w = J(n-1)+3

Even though the recursive call shows up 3 times in the algorithm, I just call it once and use the value returned in the evaluations statements.

Thanks,
katherine