Josephus Variant

158 Views Asked by At

I set myself the challenge of trying to solve a variant of the josephus problem where instead of killing every second person, every third person dies. The formula for the original sequence is $$2(n-2^ \left.\lfloor log_2 (n)\rfloor \right.) +1 $$ i have created a python 2.7 script to find theaters which i will add a link to later. I believe it is non-polynomal. Anyway, the first twenty terms are: 1,1,1,4, 3, 6, 4, 6, 9, 3, 6, 9, 12, 12, 1, 4, 7, 7, 10, 13

Edit
Just to avoid ambiguity, the killing will continue in a circle fashion until there is only one person left

Python Script

print "Josephus Problem"

#create and populate array
while True:
    a = []
    counter = 1
    limit = int(raw_input('enter limit'))

    while counter <= limit:
        a.append(counter)
        counter += 1

    #start main program loop
    counter = 1
    jump = 3 #size of jumps
    position = 1 #starting position 2nd index
    while counter < limit: #go around limit-1 times
        popped = a.pop(position) #remove from array
        print str(popped) + " removed"
        position += jump - 1
        if position >= len(a):
            position = position % len(a)

        counter += 1

    print "The remaining value is: " + str(a[0]) #print remaining array value
    print '1: again'
    print '2: exit'
    reply = raw_input('would you like to go again')
    if reply == 2:
        break