Beheading of knights, who survives?

We have a round table of n knights, where n is some positive
integer. These have failed to satisfy the expectations of the mad king
and are sentenced to death. However as an act of mercy he goes around
the table killing every other knight (starting with the second)
until only one knight remains.


The question is: which seat do you need to pick to survive?

I wrote the primitive code below to tackle this problem:

while True:
    temp_num = input("Enter the number of knights: ")
    try:
        temp_num = int(temp_num)
        if temp_num =  0 and an integer

# Create a table of knights and a temp table
knights_table = [i for i in range(1,knights_num+1)]
knights_temp_table = list(knights_table)

i = 1
while len(knights_temp_table)>1:
# print("Knights =",knights_temp_table , "(",knights_temp_table[i],")")
    knights_temp_table.pop(i)
    i = (i+1)%len(knights_temp_table)
print( "The knight who survived was no.",knights_temp_table[0] )

The code runs fine and outputs the expected values n=60> 57 and n=16 > 1
However from the code it is not clear why it works. So i had some questions below

• Could the table of knights be made using a generator?

• Is a code using try knights_temp_table[i+1] and knights_temp_table[i+2] and then iterating over the list for the exceptions clearer?

• Could one implement a linked list to make the code clearer instead of modulo?

I know the code is very simple and the problem I solved almost trivial. However any suggestions is much appreaciated since I am a semi-begginer / novice at python.
* Are there any other general suggestions to improve the code, or running speed?

Those poor knights.... what did they do to deserve that?

But, there is a mathematical treat that allows this problem to be solved in O(1) time, and space.

What does that mean? Well, it means that solving the problem for 1 knight takes just as long (and just as much memory) as solving it for 10, or 1000, or 1000000000000000 knights. How is this possible?

There's a pattern that emerges when you study this problem. If there is 1 knight, then knight 1 survives. If there's 2, then knight 1 survives, and, if we map this out for say the first 32 knights, we get:

1 -> 1
2 -> 1
3 -> 3
4 -> 1
5 -> 3
6 -> 5
7 -> 7
8 -> 1
9 -> 3
10 -> 5
11 -> 7
12 -> 9
13 -> 11
14 -> 13
15 -> 15
16 -> 1
17 -> 3
18 -> 5
19 -> 7
20 -> 9
21 -> 11
22 -> 13
23 -> 15
24 -> 17
25 -> 19
26 -> 21
27 -> 23
28 -> 25
29 -> 27
30 -> 29
31 -> 31
32 -> 1

Note that, at the powers-of-2, the surviving knight skips back to knight 1. Also, between the powers, the surviving knight increments by 2 (and is always odd).

The pattern is also easy to enumerate - find the largest power of 2 that's less than (or equal to) the count. Find how many knights there are after that power, double it, and add one.

It would look like this:

import math

def low_power(input):
    return 1 << int(math.floor(math.log(input, 2)))

def survivor(count):
    return 1 + 2 * (count - low_power(count))

So, calling survivor(16) will return 1. survivor(60) returns 57.

But, you can do crazy numbers now too, like survivor(98765432123456789) is 53415676171057707

See this code running on ideone: Knights

Note that you have now confirmed you are using Python 3.4. Python 3.1 introduced the bit_length() method. This makes the determination of the power much easier (from a programming perspective - bitlength can be thought of as an implementation of the log2):

def low_power(input):
    return 1 << (input.bit_length() - 1)

The same code running bit_length in python 3 is shown here in ideone (also contains correct parenthesis for python 3 print statements).

StackExchange Code Review Q#104645, answer score: 50