Двоичные итерации, числа Фибоначчи и пер.-ка натур. чисел

[kthxbye]

Пусть $\operatorname{wt}(n)$ это A000120, т.е. число единиц в двоичной записи $n$ (или двоичный вес $n$).

Кроме того, пусть

$$\ell(n)=\left\lfloor\log_{2} n\right\rfloor$$

а также

$$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\operatorname{mod}2.$$

Здесь $T(n,k)$ это $(k+1)$-й бит с правой стороны в двоичной записи $n$.

А теперь начнем с $T(n,\ell(n)-\operatorname{wt}(n)+m+1)$ где $m=0$ и будем применять $m:=m+1$ пока не будет достигнуто $T(n,\ell(n)-\operatorname{wt}(n)+m+1)=1$.

Пусть $a(n)$ это число итераций, необходимых для достижения $1$ в операции выше.

Пусть $b(n)=a(2n+1)$.

Последовательность начинается так:

$$1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 3, 2$$

Пусть $c(n)=\operatorname{wt}(n)-b(n)$.

Последовательность начинается так:

$$0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 2, 1, 1, 2, 3, 0, 0, 0, 0, 0$$

Пусть $d(n)$ это последовательность чисел $k$ таких, что $c(k)>0$ и $c(k-1)=c(k+1)=0$

Последовательность начинается так:

$$3, 39, 75, 143, 147, 279, 283, 291, 543, 551, 555, 563, 579, 1071, 1079, 1083, 1095, 1099, 1107, 1123$$

Пусть $e(n)=\ell(d(n))$.

Последовательность начинается так:

$$\underbrace{1}_{1}, \underbrace{5}_{1}, \underbrace{6}_{1}, \underbrace{7, 7}_{2}, \underbrace{8, 8, 8}_{3}, \underbrace{9, 9, 9, 9, 9}_{5}, \underbrace{10, 10, 10, 10, 10, 10, 10, 10}_{8}$$

Гипотеза: значения встречаемости различных элементов $e(n)$ образуют последовательность чисел Фибоначчи.

Пусть

$$f(n)=\frac{d(n)-2^{e(n)}+1}{4}$$

где $f(1)=1$.

Последовательность начинается так:

$$1, 2, 3, 4, 5, 6, 7, 9, 8, 10, 11, 13, 17, 12, 14, 15, 18, 19, 21, 25$$

Гипотеза: $f(n)$ это перестановка натуральных чисел.

Можно ли как-нибудь доказать вышеприведенные гипотезы (или хотя бы одну из них)?

[kthxbye]

Пусть $q(n)$ это A007814, максимальная степень двойки на которую делится $n$.

Тогда если начинать с $T(n,q(n)+m)$ вместо $T(n,\ell(n)-\operatorname{wt}(n)+m+1)$, то соответствующая $e(n)$ выходит следующая:

$$\underbrace{3}_{1}, \underbrace{4}_{1}, \underbrace{5}_{1}, \underbrace{6, 6}_{2}, \underbrace{7, 7, 7}_{3}, \underbrace{8, 8, 8, 8}_{4}, \underbrace{9, 9, 9, 9, 9, 9}_{6}$$

Гипотеза: значения встречаемости различных элементов $e(n)$ образуют последовательность A000930.

[kthxbye]

В посте выше можно смело заменять $q(n)$ на $0$, поскольку мы работаем только с нечетными значениями для которых $q(2n+1)=0$.

Еще очень похоже, что $f(n)-1$ это A243571. По приведенному там алгоритму генерации числа после умножения надо сортировать по возрастанию. Получается, что алгоритм из первого поста более натуральный.