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

Author

Yancheng Lu, Jul 13 2020

Keywords

• nonn

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.

Examples

			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.
		

Links

• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A006257, A334473.

Programs

Mathematica

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