Коэффициенты числа повторений членов

[kthxbye]

Пусть

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

Пусть $a(n)$ это последовательность состоящая из натуральных чисел, такая, что мы начинаем с $A:=0$ и затем для $k=0..\ell(n)$ мы пошагово повторяем следующее:

• Если $T(n,k)=1$, то $A:=\left\lfloor\frac{A}{2}\right\rfloor$; в противном случае $A:=A+1$;
• $A:=A+1$.

Тогда $a(n)$ это результирующее значение $A$.

Например для $n=18=10010_2$ будем иметь:

1. $A:=0$;
2. $T(n,0)=0$, $A:=A+1=1$, $A:=A+1=2$;
3. $T(n,1)=1$, $A:=\left\lfloor\frac{A}{2}\right\rfloor=1$, $A:=A+1=2$;
4. $T(n,2)=0$, $A:=A+1=3$, $A:=A+1=4$;
5. $T(n,3)=0$, $A:=A+1=5$, $A:=A+1=6$;
6. $T(n,4)=1$, $A:=\left\lfloor\frac{A}{2}\right\rfloor=3$, $A:=A+1=4$.

Отсюда $a(18)=4$.

Пусть

$$R(n,k)=\sum\limits_{j=2^{n-1}}^{2^n-1}[a(j)=k]$$

Гипотеза:

• $R(n,k)=0$ если $n<1$ либо $k>n$;
• $R(n,k)=1$ если $k=1$ либо $k=n$;
• $R(n,k)=R(n-1,k-1)+R(n-1,2(k-1))+R(n-1,2k-1)$ в противном случае.

Чтобы проверить данную гипотезу вы можете использовать следующую программу на PARI:

a(n) = my(A=0); for(i=0, logint(n, 2), if(bittest(n, i), A\=2, A++); A++); A
R1(n) = my(v); v=vector(n, i, sum(k=2^(n-1), 2^n-1, a(k)==i))
R(n, k) = if(k==1, 1, if(k<=n, R(n-1, k-1) + R(n-1, 2*(k-1)) + R(n-1, 2*k-1)))
R2(n) = my(v); v=vector(n, i, R(n, i))
test(n) = R1(n)==R2(n)

Существует ли способ это как-то доказать? Возможна ли замкнутая форма для $R(n,k)$?