login
Least q > 1 letting Josephus survive if he finds himself at position j in the circle of m persons, but is allowed to name the elimination parameter q such that every q-th person is executed, written as triangle T(m,j), m > 1, j <= m.
5

%I #16 Jun 23 2020 10:18:58

%S 0,2,3,5,3,2,2,4,6,10,4,5,2,3,11,3,10,8,6,2,27,11,4,6,3,7,5,2,2,19,5,

%T 7,12,4,3,9,3,7,2,42,35,11,6,5,21,8,19,5,3,2,15,9,10,7,12,16,26,24,40,

%U 7,36,2,5,4,14,12,4,9,6,26,8,11,18,13,2,3,12,7,21,10,15,11,4,5,23,13,6,12,2,18,3

%N Least q > 1 letting Josephus survive if he finds himself at position j in the circle of m persons, but is allowed to name the elimination parameter q such that every q-th person is executed, written as triangle T(m,j), m > 1, j <= m.

%C Exercise 23 associated with Chapter 1.3 in "Concrete Mathematics" about the Josephus Problem asks: "Suppose that Josephus finds himself in a given position j, but he has a chance to name the elimination parameter q such that every qth person is executed. Can he always save himself?"

%C T(1,1) is set to 0 to complete the triangle. q > 1 serves to avoid the obviously merciless choice of q = 1 in the case of Josephus being located at position m.

%D Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994, page 20.

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%e The triangle begins:

%e 0

%e 2 3

%e 5 3 2

%e 2 4 6 10

%e 4 5 2 3 11

%e 3 10 8 6 2 27

%e 11 4 6 3 7 5 2

%e 2 19 5 7 12 4 3 9

%e 3 7 2 42 35 11 6 5 21

%e 8 19 5 3 2 15 9 10 7 12

%e 16 26 24 40 7 36 2 5 4 14 12

%e 4 9 6 26 8 11 18 13 2 3 12 7

%e ...

%e 3 persons:

%e q = 2: 111 -> 101 -> 001. Position 3 survives, therefore T(3,3) = 2;

%e q = 3: 111 -> 110 -> 010. Position 2 survives, therefore T(3,2) = 3;

%e q = 4: 111 -> 011 -> 010. Position 2 survives, already covered by q = 3;

%e q = 5: 111 -> 101 -> 100. Position 1 survives, therefore T(3,1) = 5.

%Y The first column of the table is A187788.

%Y Cf. A003418, A032434, A321793, A321794.

%K nonn,tabl

%O 1,2

%A _Hugo Pfoertner_, Nov 18 2018