

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 qth person is executed, written as triangle T(m,j), m > 1, j <= m.


4



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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.


REFERENCES

Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., AddisonWesley, 1994, page 20.


LINKS

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


EXAMPLE

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.


CROSSREFS

The first column of the table is A187788.
Cf. A003418, A032434, A321793, A321794.
Sequence in context: A202694 A123221 A197032 * A254862 A322235 A172984
Adjacent sequences: A321778 A321779 A321780 * A321782 A321783 A321784


KEYWORD

nonn,tabl


AUTHOR

Hugo Pfoertner, Nov 18 2018


STATUS

approved



