# 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