圆圈上顺时---recursive solution

圆圈上顺时针排列着1,2,3,....2000 这
2000个数. 从1开始,顺时针隔一个拿走一个(1最先被拿走,下一个是3被拿走).
问最后剩下是哪一个数字.

For a general positive integer m, assume k s.t. 2^k < m <= 2^{k+1}
The answer is 2m-2^{k+1}
reason: in the first round, delete 1,3,...,2m-2^{k+1}-1,
now there are m-2^{k}+2^{k+1}-m=2^k left. Since it is a circle, rename
2m-2^{k+1}+1 to be 1, 2m-2^{k+1}+2 to be 2, and 2m-2^{k+1} to be 2^k,
now it's easy to see that the last number is 2m-2^{k+1}

the recursion formula is:
f(2n) = 2f(n); since if it is even then the odds are eliminated first and
start with the game starting with the first even number again.

f(2n+1) can be given in another way:

if n==2^k
f(2n+1)=2
else
f(2n+1)=f(2n)+2


Now the solution is:
f(2000)=16*f(125)

f(2000)=2^4(2+2^2(2+2(2+2(2+2(2)))))=1952, note f(1+2)=2