Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

"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 : really good article

and here is solution :

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

share|cite|improve this question
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
up vote 6 down vote accepted

Wikipedia provides an explicit solution for the Josephus problem (as this is called) for every 2nd elimination:

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.