I would show you what I have but I actually don't know where to start this problem..
If n people (numbered 1 to n) stand in a circle and someone starts going around the circle and eliminating every other person till only one person is left, the number J(n) of the person left at the end is given by
J(n) = 1 if n = 1
J(n) = 2*J(n/2) - 1 if n > 1 and n is even
J(n) = 2*J((n-1)/2) + 1 if n > 1 and n is odd
(i) Write a recursive procedure to compute J. [As a check the first 16 values (starting with 1) of J(n) are 1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1].
(ii)Compute the value of J(10000).
(iii) Can you explain why this is so much faster than our recursive procedure to compute the n-th Fibonacci number?