$\DeclareMathOperator\wt{wt}$Let $\wt(n)$ be [A000120](https://oeis.org/A000120), number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).


Let $f(n)$ be [A007814](https://oeis.org/A007814), the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.


Also
$$n=2^{t\_1}(1+2^{t\_2+1}(1+\dotsb(1+2^{t\_{wt(n)}+1}))\dotsb).$$
Then we have an integer sequence given by
$$a(n)=\sum\limits\_{j=0}^{2^{\wt(n)}-1}(-1)^{\wt(n)-\wt(j)}\prod\limits\_{k=0}^{\wt(n)-1}\left(1+f\left(\left\lfloor\frac{j}{2^k}\right\rfloor+1\right)\right)^{t\_{k+1}+1},\quad a(0)=1.$$
Let
$$s(n)=\sum\limits\_{k=0}^{2^n-1}a(k).$$
Then I conjecture that $s(n)$ is [A095989](https://oeis.org/A095989), INVERTi transform applied to the ordered Bell numbers.


I also conjecture that
\begin{align}
a(0)=a(1)&=1\\
a(2n+1) &= a(2n)\\
a(2n)& = a(n)+a(2n-2^{f(n)})+b(n-1)\\
b(2n+1) &= b(n)\\
b(2n) &= a(2n).
\end{align}
In other words
\begin{align}
a(2n) &= c(n)\\
c(0)&=1\\
c(n)& = c\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+c\left(\left\lfloor\frac{2n-2^{f(n)}}{2}\right\rfloor\right)+c(g(n-1))
\end{align}
where $g(n)$ is [A025480](https://oeis.org/A025480), $g(2n) = n$, $g(2n+1) = g(n)$.


Is there a way to prove it? Is it possible to at least get a closed form for $s(n)$?


Similar questions:


* [Sum with Stirling numbers of the second kind](https://mathoverflow.net/questions/406738/sum-with-stirling-numbers-of-the-second-kind)
* [Recurrence for the sum](https://mathoverflow.net/questions/405174/recurrence-for-the-sum)
* [Pair of recurrence relations with $a(2n+1)=a(2f(n))$](https://mathoverflow.net/questions/406902/pair-of-recurrence-relations-with-a2n1-a2fn)
* [Sequences that sums up to second differences of Bell and Catalan numbers](https://mathoverflow.net/questions/407758/sequences-that-sums-up-to-second-differences-of-bell-and-catalan-numbers)



Sequence that sums up to INVERTi transform applied to the ordered Bell numbers
First, we let $P(j,k):=1+f(\lfloor\tfrac{j}{2^k}\rfloor+1)$ and sum over $n$ of fixed weight $\ell:=\mathrm{wt}(n)$ (like in [this answer](https://mathoverflow.net/q/406817)):
\begin{split}
s(n) &= \sum\_{\ell=0}^n \sum\_{t\_1 + \dots + t\_\ell \leq n-\ell}
\sum\_{j=0}^{2^\ell-1} (-1)^{\ell-\mathrm{wt}(j)} \prod\_{k=0}^{\ell-1} P(j,k)^{t\_k+1} \\
&= [x^{n+1}]\ \sum\_{\ell=0}^n \sum\_{j=0}^{2^\ell-1} (-1)^{\mathrm{wt}(j)+1} \prod\_{k=0}^{\ell} \frac{-P(j,k)x}{1-xP(j,k)}.
\end{split}


Now, we notice that $P(j,k)$ depends on runs of unit bits in $j$. Namely, each run of length $u-1$ contributes the term
$$\prod\_{v=1}^{u} \frac{-vx}{1-vx} = x^{u} (-1)^{u} u! \prod\_{v=1}^{u} \frac1{1-vx}.$$
Hence, introducing the number $z$ of zero bits in $j$ padded with an extra zero at the beginning (and so $\mathrm{wt}(j)=\ell+1-z$), we have
\begin{split}
s(n) &= [x^{n+1}]\ \sum\_{\ell=0}^n [y^{\ell+1}]\ \sum\_{z\geq 0} (-1)^{\ell+2-z} \left(\sum\_{u\geq 1} y^u (-1)^u x^u u! \prod\_{v=1}^u \frac1{1-vx}\right)^z\\
&= -[x^{n+1}]\ \sum\_{\ell=0}^n (-1)^{\ell+1} [y^{\ell+1}]\ \left(1+\sum\_{u\geq 1} y^{u} (-1)^u x^u u! \prod\_{v=1}^u \frac1{1-vx}\right)^{-1}\\
&=- [x^{n+1}]\ \left(1+\sum\_{u\geq 1} x^u u! \prod\_{v=1}^u \frac1{1-vx}\right)^{-1}\\
&=- [x^{n+1}]\ \left(1+\sum\_{u\geq 1} x^u u! \sum\_{m\geq 0} S(m,u) x^{m-u}\right)^{-1}\\
&=- [x^{n+1}]\ \left(1+\sum\_{m\geq 1} x^m B\_m^o\right)^{-1},
\end{split}
which can be recognized as INVERTi transform of ordered Bell numbers $B\_m^o$.


