Принадлежность n посл.-ти A333975

[kthxbye]

Задача предельно проста: определите принадлежность некоторого числа $n$ последовательности A333975.

Сама последовательность задана следующим образом: $a(1)=1, a(2)=2$, а каждый следующий член - это наименьшее число, которое не принадлежит множеству значений $a(i) \operatorname{OR} a(j)$. Последнее мы получаем с использованием всех возможных пар $\left\lbrace i,j\right\rbrace$ с условием, что $1\leqslant i<j<n$. Здесь $\operatorname{OR}$ это оператор "или".

[zykov]

kthxbye в сообщении #1560214 писал(а):

Здесь $\operatorname{OR}$ это оператор "или".

Операция "ИЛИ" применённая побитно к двоичному представлению двух чисел.

[kthxbye]

zykov в сообщении #1560215 писал(а):

kthxbye в сообщении #1560214 писал(а):

Здесь $\operatorname{OR}$ это оператор "или".

Операция "ИЛИ" применённая побитно к двоичному представлению двух чисел.

Да, все верно. Благодарю за уточнение.

Небольшая подсказка: минимальное число аналогичных сравнений, которые необходимо выполнить, чтобы определить принадлежность, равно

$$\ell(\ell(n+1)+1)$$

где

$$\ell(n)=\left\lfloor\log_2(n)\right\rfloor$$

[Null]

Сумма цифр числа в двоичной системе $2^k-1$?

[kthxbye]

Null в сообщении #1560488 писал(а):

Сумма цифр числа в двоичной системе $2^k-1$?

Да, это тоже решение, и оказывается его находит даже Sequence Machine: http://sequencedb.net/s/A333975. У меня немного другое, и, как было отмечено выше, оно требует большего количества проверок с ростом $n$.