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

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

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

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