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.

2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881, 13482720, 25779600, 68468401, 610346880, 1271932200, 327280800, 11605393800, 10071626400, 270022896000, 212719197601, 673534461600, 80276676481, 7618206526561, 14227357636801

Offset: 1

Author

Nicholas Matteo, Apr 29 2021

Keywords

• nonn

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.

Examples

			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.
		

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.
• Index entries for sequences related to the Josephus Problem
• Bert Dobbelaere, Python program

Crossrefs

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

Cf. A006257, last survivor with q = 2.

Cf. A054995, last survivor with q = 3.

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

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

Programs

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

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