Uncrossed Sequence Calculation
algorithm, math
Solution
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 [nphi], we can approximate phi as a ratio of consecutive fibonacci numbers, giving an O(lognloglogn) algorithm. (O(logn) time to do arithmetic on O(log n) bit numbers).
Problem
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.