Расчет некроссированной последовательности

Question

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

Последовательность A определяется следующим образом:

Начинаются с натуральных чисел 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.
    }

Дайте быстрый алгоритм для определения A [n], учитывая n.

Попробуйте получить алгоритм, полиномиальный по log n.

Answer 1

Извините за публикацию этого вопроса.

По-видимому, это известная последовательность, называемая последовательностью Витоффа, и существует аккуратная формула для A [n], заданная как A [n] = [n * phi], где [x] = интегральная часть x, а phi - золотое сечение .

Чтобы вычислить [n phi], мы можем аппроксимировать phi как отношение последовательных чисел Фибоначчи, давая алгоритм O (logn loglogn). (O (logn) время для выполнения арифметических операций с O (log n) битами).

Answer 2

Вот как это начинается

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

число 1 никогда не пересекается, потому что наименьшее число, которое можно пересечь, это 1 + 1 == 2.

Таким образом, существует алгоритм с постоянным временем: A [n] = 1 для всех n.