A336233 a(n) is the player who has highest winning probability in the "Random Josephus Game" with n players.

1, 1, 3, 1, 2, 3, 4, 6, 8, 1, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 23, 25, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 36, 37, 39, 41, 42, 44, 46, 47, 49, 51, 53, 55, 56, 58, 60, 62, 64, 66, 68

Offset

1,3

Comments

The "Random Josephus Game" is a random variety of Josephus problem. Here, there are n players arranged in a loop labeled 1,2,...,n, and on every player's turn, he kills one of the players except himself equiprobably randomly and then gives the turn to the next living player in order of the loop, started by player 1. The winner is the last survivor.

Note that in the case with 3 players, both player 2 and player 3 have a winning probability of 1/2, and a(3) can be either 2 or 3.

Links

Table of n, a(n) for n=1..74.

Index entries for sequences related to the Josephus Problem

Example

For example, a "Random Josephus Game" with 4 players has 6 possible results, the probability of each is 1/6 respectively:
1) Player 1 kills player 2 and gives the turn to player 3. Then player 3 kills player 4 and gives the turn to player 1. Finally, player 1 kills player 3 and becomes the winner.
2) Player 1 kills player 2 and gives the turn to player 3. Then player 3 kills player 1 and gives the turn to player 4. Finally, player 4 kills player 3 and becomes the winner.
3) Player 1 kills player 3 and gives the turn to player 2. Then player 2 kills player 4 and gives the turn to player 1. Finally, player 1 kills player 2 and becomes the winner.
4) Player 1 kills player 3 and gives the turn to player 2. Then player 2 kills player 1 and gives the turn to player 4. Finally, player 4 kills player 2 and becomes the winner.
5) Player 1 kills player 4 and gives the turn to player 2. Then player 2 kills player 3 and gives the turn to player 1. Finally, player 1 kills player 2 and become the winner.
6) Player 1 kills player 4 and gives the turn to player 2. Then player 2 kills player 1 and gives the turn to player 3. Finally, player 3 kills player 2 and becomes the winner.
One can see, player 1 wins in three of the cases above, while player 3 wins in one of those, player 4 wins in two, and Player 2 wins in none. Thus, the winning probability of the four players are 1/2, 0, 1/6 and 1/3 respectively. Therefore a(4)=1.

Mathematica

table1 = NestList[
  Prepend[(Range[0, Length[#] - 1] Prepend[Most[#], 0] +
       Range[Length[#] - 1, 0, -1] #)/Length[#], Last[#]] &, {1.},
  1000];
First[Ordering[#, -1]] & /@ table1

Crossrefs

Cf. A006257, A334473.

Sequence in context: A260313 A050056 A209882 * A325845 A260116 A173234

Adjacent sequences: A336230 A336231 A336232 * A336234 A336235 A336236

Keyword

nonn

Author

Yancheng Lu, Jul 13 2020

Status

approved