<s>[INST] Coefficients of number of the same terms which are arising from iterations based on binary expansion of $n$ Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
Let
$$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\operatorname{mod}2$$
Here $T(n,k)$ is the $(k+1)$-th bit from the right side in the binary expansion of $n$.
Let $a(n)$ be the sequence of positive integers such that we start from $A:=0$ and then for $k=0..\ell(n)$ we iterate:

*

*If $T(n,k)=1$, then $A:=\left\lfloor\frac{A}{2}\right\rfloor$;
otherwise $A:=A+1$;

*$A:=A+1$.

Then $a(n)$ is the resulting value of $A$.
For example for $n=18=10010_2$ we have:

*

*$A:=0$;

*$T(n,0)=0$, $A:=A+1=1$, $A:=A+1=2$;

*$T(n,1)=1$, $A:=\left\lfloor\frac{A}{2}\right\rfloor=1$, $A:=A+1=2$;

*$T(n,2)=0$, $A:=A+1=3$, $A:=A+1=4$;

*$T(n,3)=0$, $A:=A+1=5$, $A:=A+1=6$;

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

Then $a(18)=4$.
Let
$$R(n,k)=\sum\limits_{j=2^{n-1}}^{2^n-1}[a(j)=k]$$
I conjecture that

*

*$R(n,k)=0$ if $n<1$ or $k>n$;

*$R(n,k)=1$ if $k=1$ or $k=n$;

*$R(n,k)=R(n-1,k-1)+R(n-1,2(k-1))+R(n-1,2k-1)$ otherwise.

To verify this conjecture one may use this PARI prog:
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)

Is there a way to prove it? Is there a suitable closed form for $R(n,k)$?
 [/INST] In other words, if $(b_\ell b_{\ell-1}\dots b_0)_2$ is the binary representation of $n$, then
$$a(n) = g(g(\dots g(g(0,b_0),b_1)\dots ),b_{\ell-1}), b_\ell),$$
where
$$g(A,b) = \begin{cases} A+2, &\text{if } b=0;\\
\left\lfloor \frac{A+2}2\right\rfloor, &\text{if } b=1.
\end{cases}$$
Consider a number triangle obtained from $A=0$ by iteratively applying $g(\cdot,0)$ and $g(\cdot,1)$:
$$
\begin{gathered}
         0 \\
     1   \ \ \ \ \ \ \ \ 2 \\
   1 \ \ \ \ 3 \ \ \ \ 2 \ \ \ \ 4 \\
  1\ 3\ 2\ 5\ 2\ 4\ 3\ 6 \\
\dots
\end{gathered}
$$
Let $f(n,k)$ be the multiplicity of $k$ at the level $n\in\{0,1,2\dots\}$ in this triangle.
It is easy to see that each number $k\geq 1$ in this triangle may result only from the following numbers in the previous row: $2k-2$, $2k-1$, or $k-2$, implying that $f$ satisfies the recurrence formula:
$$f(n,k) = \begin{cases} 
\delta_{k,0}, & \text{if }n=0; \\
f(n-1,2k-2) + f(n-1,2k-1) + f(n-1,k-2), & \text{if }n>0.
\end{cases}$$
The quantity $R(n,k)$ accounts for numbers $k$ in the $n$th row, but only for those that resulted from $g(\cdot,1)$, that is
$$R(n,k) = f(n-1,2k-2) + f(n-1,2k-1).$$
Expanding this formula using the recurrence for $f$, we get
\begin{split}
R(n,k) &= f(n-2,4k-5) + f(n-2,4k-6) + f(n-2,2k-4) \\
&\quad + f(n-2,4k-3) + f(n-2,4k-4) + f(n-2,2k-3) \\
&= R(n-1,2k-2) + R(n-1,2k-1) + R(n-1,k-1).
\end{split}
QED
</s>