OFFSET
1,1
COMMENTS
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.
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)).
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.
Schumer (2002) mentions this version along with more variants (e.g., eliminating all odd-numbered people first) in the section "Subsets marked for elimination".
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.
REFERENCES
R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994, p. 20.
W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover, 1987, pp. 32-36.
LINKS
Bert Dobbelaere, Table of n, a(n) for n = 1..40
P. Schumer, The Josephus Problem: Once More Around, Mathematics Magazine, Vol. 75:1 (2002), 12-17.
Bert Dobbelaere, Python program
EXAMPLE
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.
PROG
(Python)
def A343780(n):
q = 1
while True:
s, c = [1]*n+[0]*n, 0
for i in range(n):
c = (c+q)%(2*n-i)
if s[c]: break
s = s[:c]+s[c+1:]
else:
return q+1
q += 1 # Chai Wah Wu, Apr 30 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Nicholas Matteo, Apr 29 2021
EXTENSIONS
a(17)-a(21) from Chai Wah Wu, Apr 30 2021
a(22) from Nicholas Matteo, Apr 30 2021
a(23)-a(25) from Jon E. Schoenfield, Apr 30 2021
a(26)-a(27) from Bert Dobbelaere, May 01 2021
STATUS
approved