The famous Josephus problem

josephus.py

# There are n men numbered 1 through n standing in a circle. Starting
# from the first, every m-th man is killed, continuing the process
# from the next man in the circle. Who is the last to be killed?

# recursive
def l(n, m):
    if n == 1: return 0
    f = (m-1) % n
    k = l(n-1, m)
    if k <= n-1-(f+1): return k+f+1
    return k-(n-f-1)
def L(n, m): return 1 + l(n, m)

# iterative
def l0(N, m):
    k = 0
    for n in range(2, N+1):
        f = (m-1) % n
        k = k+f+1 if k <= n-1-(f+1) else k-(n-f-1)
    return k
def L0(n, m): return 1 + l0(n, m)

n, m = 10**6, 2
print(L0(n, m))