There is a stack of cards numbered in order from 1 to n.
The first card is placed at the bottom of the stack.
The second card is removed.
Cards are alternately placed at the bottom and removed until only one card remains.
Which card is it?
The first 100 (I add a zero at the beginning since lists are zero based in Python):
[0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71]
This is in oeis as A006257
Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1
Whenever n is 2^k the value is 1, and then the value increases by 2 until the next power of 2 is reached.
------------
ans = [0]
for n in range(1,100):
deck = [i for i in range(1,n+1)]
for k in range(n-1):
deck = deck[1:] + deck[:1]
deck.pop(0)
ans.append(deck[0])
print(ans)
|
|
Posted by Larry
on 2023-08-09 09:15:28 |
Solution
