login
If n good guys followed by n bad guys stand in a circle, a(n) is the least q such that executing every q-th person gets all bad guys first.
1

%I #64 May 05 2021 21:07:08

%S 2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,

%T 13482720,25779600,68468401,610346880,1271932200,327280800,

%U 11605393800,10071626400,270022896000,212719197601,673534461600,80276676481,7618206526561,14227357636801

%N If n good guys followed by n bad guys stand in a circle, a(n) is the least q such that executing every q-th person gets all bad guys first.

%C There are 2n people in a circle, numbered 1 through 2n; the first n are "good guys" and the last n are "bad guys." We count, starting from 1, to the q-th person, who is executed; then, starting from the next position, repeat until all bad guys are gone.

%C This is a variant of the Josephus problem. In exercise 1.21 of Concrete Mathematics, it is proved there is always a q such that all bad guys are executed before any good guys, namely the least common multiple of n+1, n+2, ..., 2n (which provides an upper bound for a(n)).

%C According to Ball and Coxeter, in medieval times this was called the "Turks and Christians problem", described as n Turks and n Christians aboard a ship in a storm, which will sink unless half the passengers are thrown overboard; every q-th person will be tossed in the sea.

%C Schumer (2002) mentions this version along with more variants (e.g., eliminating all odd-numbered people first) in the section "Subsets marked for elimination".

%C Graham, Knuth and Patashnik say a non-rigorous argument suggests that a "random" value of q will succeed with probability (n/(2n)) * ((n-1)/(2n-1)) * ... * (1/(n+1)) = 1/binomial(2n,n) ~ sqrt(Pi*n)/4^n, so we might expect to find such a q less than 4^n (page 500). All the known values of a(n) are (much) less than 4^n.

%D R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994, p. 20.

%D W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover, 1987, pp. 32-36.

%H Bert Dobbelaere, <a href="/A343780/b343780.txt">Table of n, a(n) for n = 1..40</a>

%H P. Schumer, <a href="http://www.jstor.org/stable/3219179">The Josephus Problem: Once More Around</a>, Mathematics Magazine, Vol. 75:1 (2002), 12-17.

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

%H Bert Dobbelaere, <a href="/A343780/a343780.py.txt">Python program</a>

%e For n = 2, we have four people; with q = 7 we count 1,2,3,4,1,2,3 and person 3 is eliminated. Next we count 4,1,2,4,1,2,4, so person 4 is eliminated, leaving only 1 and 2. Attempting this with any q < 7 does not eliminate 3 and 4 first.

%o (Python)

%o def A343780(n):

%o q = 1

%o while True:

%o s, c = [1]*n+[0]*n, 0

%o for i in range(n):

%o c = (c+q)%(2*n-i)

%o if s[c]: break

%o s = s[:c]+s[c+1:]

%o else:

%o return q+1

%o q += 1 # _Chai Wah Wu_, Apr 30 2021

%Y Cf. A198791, least q eliminating the odd-numbered people.

%Y Cf. A006257, last survivor with q = 2.

%Y Cf. A054995, last survivor with q = 3.

%Y Cf. A321781, least q leaving position j as last survivor.

%Y Cf. A321793, maximum q needed to ensure survival of one of n people.

%K nonn

%O 1,1

%A _Nicholas Matteo_, Apr 29 2021

%E a(17)-a(21) from _Chai Wah Wu_, Apr 30 2021

%E a(22) from _Nicholas Matteo_, Apr 30 2021

%E a(23)-a(25) from _Jon E. Schoenfield_, Apr 30 2021

%E a(26)-a(27) from _Bert Dobbelaere_, May 01 2021