# Is there efficient way of finding last number in following sequence

"Imagine the sequence lying on a circle. Take every second number in the sequence. Continue the process until you finish"

Is there efficient way of finding last number in following sequence :

we have numbers $1,2,...n$, we delete $2,4,...,$ and start it again so

$n=2$ gives $2$

$n=10$ gives $5$, because : $2,4,6,8,10,3,7,1,9,5$

$n=25$ gives $19 2,4,6,8,10,12,14,16,18,20,22,24,1,5,9,13,17,21,25,7,15,23,11,3,19$

is there any short way to for calculationg last number for given $n$ ? Ive some clues when I look at $n=2^k$

edition : http://mathworld.wolfram.com/JosephusProblem.html really good article

and here is solution :

http://oeis.org/A032434

answer is : (1+2*n-pow(2,1+floor(log2(n)))

-
Could you explain a bit more about what exactly the algorithm does? It is not clear to me. – Tobias Kildetoft Mar 20 '13 at 15:19
Imagine the sequence lying on a circle. Start from 2, Take every second number in the sequence and delete them at each step. Continue the process until you finish. – muzzlator Mar 20 '13 at 15:21
I feel kind of bad for saying "delete them at each step" after reading the anecdote – muzzlator Mar 20 '13 at 15:26

## 1 Answer

Wikipedia provides an explicit solution for the Josephus problem (as this is called) for every 2nd elimination: en.wikipedia.org/wiki/Josephus_problem.

There is also a more general discussion on eliminating with less frequency....

-
And the Josephus problem figures prominently in Concrete Mathematics by Graham, Knuth, Patashnik. – Marc van Leeuwen Mar 20 '13 at 21:28
@MarcvanLeeuwen Yes, that's where I remembered the name from. – gt6989b Mar 20 '13 at 21:29