A187788 -id:A187788 - cp's OEIS frontend

A187789 a(n) is the start position for a Sankt-Petrus-game with n white and n black stones and the least step A187788(n).

2, 3, 2, 8, 5, 5, 2, 7, 1, 17, 15, 4, 8, 1, 2, 30, 26, 11, 35, 7, 26, 27, 23, 44, 24, 30, 6, 39, 53, 18, 2, 15, 61, 40, 30, 68, 44, 32, 78, 29, 81, 15, 19, 76, 51, 67, 40, 19, 53, 42, 53, 3, 74, 103, 73, 35, 105, 78, 110, 105, 76, 61, 2, 5, 48, 128, 82, 36, 37, 63, 88, 87, 31, 123, 93, 126, 2, 1, 156, 89, 33, 160, 90, 135, 124, 136, 145, 79, 42, 26, 104, 94, 67, 44, 186, 30, 133, 137, 40, 118

Offset: 1

Paul Weisenhorn, Jan 06 2013

nonn

Beginning at the position a(n) with the least step A187788(n) (n-1) white stones were eliminated; then starting at the position 1 of the last white stone, n black stones were eliminated.

			n=8; WWBBWBBWWBBWWBWB; step=A187788(8)=3; start=a(8)=7; elimination: white stones: {9,12,15,2,5,8,13}, black stones: {4,10,16,6,14,7,3,11}.

W. Ahrens, Das Josephusspiel, Archiv für Kulturgeschichte, Jg 11(1913), 129-151.

R. Baumann, Das Josephus-Problem, LOG IN, Heft Nr. 165, pp. 68-71, 2010 (in German).
Index entries for sequences related to the Josephus Problem

Cf. A187788, A206602.

stone:=proc(n1)
local n,j,k,h,z,zp: global a,m,s:
n:=2*n1: m:=m+1:
for j from 1 to n-1 do z[j]:=z[j]+1: end do:
z[n]:=1: zp:=1:
for j from 1 to n1 do
for k from 1 to (s-2) do  zp:=z[zp]: end do:
  h:=z[zp]: z[zp]:=z[z[zp]]: zp:=z[zp]:
end do:
if (h=1) then a[n1]:=1: else a[n1]:=n+2-h: end if:
end proc:
m:=0: s:=1:
while (m < 100) do
s1:=s: s:=s+1: c:=1:
for p from 2 to 100 by 2 do  p1:=p-1: p2:=p+1:
  b:=(c+s1) mod p +1:
  if (b=1) and (a[p1]=0) then stone(p1): end if:
  c:=(b+s1) mod p2 +1:
  if (c=1) and (a[p]=0) then stone(p): end if:
end do:
end do:

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.

Original entry on oeis.org

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

Hugo Pfoertner, Nov 18 2018

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.

			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.

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

Index entries for sequences related to the Josephus Problem

The first column of the table is A187788.

Cf. A003418, A032434, A321793, A321794.

cp's OEIS Frontend

A187789 a(n) is the start position for a Sankt-Petrus-game with n white and n black stones and the least step A187788(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple