Eliminating with a Python list

The four tools that suffice

The assignment requires nothing exotic. For an object L of type list in Python:

   L[i]      accesses the element at index i (the first has index 0)
   del L[i]  removes the element at index i, the list closes up
   len(L)    returns the number of elements
   a % b     remainder of the Euclidean division of a by b

Example: if L = [1, 2, 3], then after del L[1] the list is [1, 3].

Modelling the circle

A circle does not exist in Python — but a list plus the % operator is enough: when the index runs past the end, the modulo brings it back to the start. That is exactly what a circle does.

   personnes = list(range(1, n + 1))   # the numbers 1, 2, …, n
   i = 0                               # position of the last eliminated

Stepping k at a time

At each round we advance k places from the current position. Since the eliminated person disappears from the list, the index i already points at the next one after the del: so we must advance by k − 1 places, not k.

   i = (i + k - 1) % len(personnes)
   del personnes[i]

That single line contains the whole problem. It is repeated as long as more survivors remain than wanted.

Complexity

del L[i] copies the tail of the list: each removal costs at worst n operations, so the full simulation is O(n²). For n = 41 or n = 100 this is instantaneous; for n = 10⁶ another data structure would be needed. This is also what motivates the search for an exact formula in the following parts.