cp's OEIS Frontend

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

%I A343780 #64 May 05 2021 21:07:08
%S A343780 2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,
%T A343780 13482720,25779600,68468401,610346880,1271932200,327280800,
%U A343780 11605393800,10071626400,270022896000,212719197601,673534461600,80276676481,7618206526561,14227357636801
%N A343780 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 A343780 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 A343780 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 A343780 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 A343780 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 A343780 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 A343780 R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994, p. 20.
%D A343780 W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover, 1987, pp. 32-36.
%H A343780 Bert Dobbelaere, <a href="/A343780/b343780.txt">Table of n, a(n) for n = 1..40</a>
%H A343780 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 A343780 <a href="https://oeis.org/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%H A343780 Bert Dobbelaere, <a href="/A343780/a343780.py.txt">Python program</a>
%e A343780 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 A343780 (Python)
%o A343780 def A343780(n):
%o A343780     q = 1
%o A343780     while True:
%o A343780         s, c = [1]*n+[0]*n, 0
%o A343780         for i in range(n):
%o A343780             c = (c+q)%(2*n-i)
%o A343780             if s[c]: break
%o A343780             s = s[:c]+s[c+1:]
%o A343780         else:
%o A343780             return q+1
%o A343780         q += 1 # _Chai Wah Wu_, Apr 30 2021
%Y A343780 Cf. A198791, least q eliminating the odd-numbered people.
%Y A343780 Cf. A006257, last survivor with q = 2.
%Y A343780 Cf. A054995, last survivor with q = 3.
%Y A343780 Cf. A321781, least q leaving position j as last survivor.
%Y A343780 Cf. A321793, maximum q needed to ensure survival of one of n people.
%K A343780 nonn
%O A343780 1,1
%A A343780 _Nicholas Matteo_, Apr 29 2021
%E A343780 a(17)-a(21) from _Chai Wah Wu_, Apr 30 2021
%E A343780 a(22) from _Nicholas Matteo_, Apr 30 2021
%E A343780 a(23)-a(25) from _Jon E. Schoenfield_, Apr 30 2021
%E A343780 a(26)-a(27) from _Bert Dobbelaere_, May 01 2021