Uncrossed Sequence Calculation

Question

From http://discuss.joelonsoftware.com/default.asp?interview.11.794054.1

The sequence A is defined as follows:

Start with the natural numbers 1,2,3,...

Initialize count = 1;

    while(there are uncrossed numbers)
    {
        pick the first uncrossed number say n.
      set A[count] = n.
      Cross out the number count+n.
      Cross out the number n
      Increment count.
    }

Give a fast algorithm to determine A[n], given n.

Try getting an algorithm which is polynomial in log n.

Answer 1

Here is how it starts

1 2 3 4 5 6 7 8 ... A[1] = 1, cross 2
1 X 3 4 5 6 7 8 ... A[2] = 1, cross 3
1 X X 4 5 6 7 8 ... A[3] = 1, cross 4
...

number 1 is never crossed because the least number that can be crossed is 1+1==2.

So there is constant time algorithm: A[n] = 1 for all n.

Answer 2

Sorry for posting this question.

Apparently this is a famous sequence called Wythoff's sequence and there is a neat formula for A[n] given by A[n] = [n*phi] where [x] = integral part of x and phi is the golden ratio.

To calculate [n*phi], we can approximate phi as a ratio of consecutive fibonacci numbers, giving an O(logn*loglogn) algorithm. (O(logn) time to do arithmetic on O(log n) bit numbers).