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)$?