A321781 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.

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, 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, 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

Offset: 1

Author

Hugo Pfoertner, Nov 18 2018

Keywords

• nonn
• tabl

Comments

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?"

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.

Examples

			The triangle begins:
   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  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  7 36  2  5  4 14 12
   4  9  6 26  8 11 18 13  2  3 12  7
   ...
3 persons:
  q = 2: 111 -> 101 -> 001. Position 3 survives, therefore T(3,3) = 2;
  q = 3: 111 -> 110 -> 010. Position 2 survives, therefore T(3,2) = 3;
  q = 4: 111 -> 011 -> 010. Position 2 survives, already covered by q = 3;
  q = 5: 111 -> 101 -> 100. Position 1 survives, therefore T(3,1) = 5.
		

References

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

Links

• Index entries for sequences related to the Josephus Problem

Crossrefs

The first column of the table is A187788.

Cf. A003418, A032434, A321793, A321794.