# A343780 - If n good guys followed by n bad guys stand in a circle, the least q such 
# that executing every q-th person gets all bad guys first. 
# Python program by Bert Dobbelaere

def depth( ngood, nbad, position, qminus1):
	rv=0
	while True:
		m=ngood+nbad
		r=(position+qminus1)%m
		if r < ngood:
			return rv
		rv+=1 ;	nbad-=1 ; position=r

def increaseWheelModulus(in_list, in_modulus, allowedresidues, inc_modulus):
	out_list=[]
	f=1
	while (f*in_modulus)%inc_modulus != 0:
		f+=1
	
	for k in range(f):
		for r in in_list:
			r0=k*in_modulus+r
			if allowedresidues[r0%inc_modulus]:
				out_list.append(r0)
	return out_list, in_modulus*f

STOPLENGTH=10000000 # Stop growing our modulus and list of residues if this value is exceeded (performance/memory tradeoff)

n=1
while True:
	lst,M = [0],1
	nbad=1
	while nbad<=n and len(lst)<STOPLENGTH:
		allowed=bytearray(n+nbad)
		for k in range(nbad):
			# Because the way the puzzle is defined, the bad guys form one contiguous block around the circle
			# After eliminating a bad guy, our position is somewhere in the "bad" zone and the number of bads left sets 
			# a bound to how far (clockwise or counterclockwise) the other ones can maximally be.
			allowed[k]=1
			allowed[n+k]=1
		lst,M = increaseWheelModulus(lst,M, allowed ,n+nbad)
		nbad+=1
	print("n=%d, checking %d values modulo %d"%(n,len(lst),M))
	offset=0
	found=False
	while not found:
		for r in lst:
			qm1 = offset+r
			if depth(n,n,0,qm1)==n:
				print("A343780(%d) = %d"%(n,qm1+1))
				found=True
				break
		offset+=M
	n+=1