Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

"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)))

share|improve this question
2  
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
1  
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
3  
    
I feel kind of bad for saying "delete them at each step" after reading the anecdote –  muzzlator Mar 20 '13 at 15:26
add comment

1 Answer

up vote 6 down vote accepted

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....

share|improve this answer
1  
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
add comment

Your Answer

 
discard

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.