000RM.dvi

37.2 Generalized Josephus problemJ(n, k) 1003

37.2 Generalized Josephus problemJ(n, k)

J(10,3):

1

2

4 3

5

6

7

8 9

10

6

4

* 1

8

2

5

(^73)
9
J(10,k)for various values ofk
Forn=10, here are the sequences of execution depending on the values
ofk. The last column gives the survivors.
k ∗
1 1 2 345 6 7 8 9 10
2 24681037195
3 3 6 927 1 8 510 4
4 4 8 273109 1 6 5
5 510629 8 1 4 7 3
6 62975811043
7 7 4 213 6105 8 9
8 86571032941
9 98102534167
10 10136295748
Positions 2 and 6 aredeadlypositions for the Josephus problem of 10
prisoners and random choice ofk.