Beheading of knights, who survives?
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 -&gt; 1
2 -&gt; 1
3 -&gt; 3
4 -&gt; 1
5 -&gt; 3
6 -&gt; 5
7 -&gt; 7
8 -&gt; 1
9 -&gt; 3
10 -&gt; 5
11 -&gt; 7
12 -&gt; 9
13 -&gt; 11
14 -&gt; 13
15 -&gt; 15
16 -&gt; 1
17 -&gt; 3
18 -&gt; 5
19 -&gt; 7
20 -&gt; 9
21 -&gt; 11
22 -&gt; 13
23 -&gt; 15
24 -&gt; 17
25 -&gt; 19
26 -&gt; 21
27 -&gt; 23
28 -&gt; 25
29 -&gt; 27
30 -&gt; 29
31 -&gt; 31
32 -&gt; 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 &lt;&lt; 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 &lt;&lt; (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).