- Let $a(n)$ be A347205. Here $$ a(2^m(2k+1)) = \sum\limits_{j=0}^{m}a(2^j k), \\ a(0) = 1. $$
- Let $\nu_2(n)$ be A007814 (i.e., number of trailing zeros in the binary expansion of $n$). Here $$ \nu_2(2n+1) = 0, \\ \nu_2(2n) = \nu_2(n) + 1. $$ Using $\nu_2(n)$ we can rewrite recurrence for $a(n)$ as $$ a(2n+1) = a(n), \\ a(2n) = a(n) + a(n - 2^{\nu_2(n)}), \\ a(0) = 1. $$
- Let $\operatorname{wt}(n)$ be A000120 (i.e., number of ones in the binary expansion of $n$). Here $$ \operatorname{wt}(2n+1) = \operatorname{wt}(n) + 1, \\ \operatorname{wt}(2n) = \operatorname{wt}(n), \\ \operatorname{wt}(0) = 0. $$
- Let $R(n, x)$ be the family of row polynomials such that $$ R(2n+1, x) = xR(n, x), \\ R(2n, x) = R(n, x) + R(n - 2^{\nu_2(n)}, x), \\ R(0, x) = x. $$
- Let $T(n, k)$ be an integer coefficients such that $$ T(2n+1, k) = [1 \leqslant k \leqslant (\operatorname{wt}(n) + 1)]T(n, k), \\ T(2n+1, \operatorname{wt}(n) + 2) = T(n, \operatorname{wt}(n) + 1), \\ T(2n, k) = [1 \leqslant k \leqslant (\operatorname{wt}(n) + 1)]\sum\limits_{i=1}^{k} T(n, i), \\ T(0, 1) = 1. $$ Here square bracket denotes Iverson bracket.
I conjecture that $$ T(n, k) = [x^{\operatorname{wt}(n) - k + 2}]R(2n, x). $$
I also conjecture that for $0 \leqslant q < 2^m$ we have $$ \sum\limits_{i}a(2^m(2^{i-1}-1)+q)[x^i]R(n,x) = a(2^m n + q). $$
Here is the PARI/GP program to check it numerically:
a(n) = if(n == 0, 1, if(n%2, a(n\2), a(n/2) + a(n/2 - 1<<(valuation(n, 2)-1))))
upto1(n, x) = my(v1); v1 = vector(n+1, i, 0) ; v1[1] = x; for(i=1, n, v1[i+1] = if(i%2, x*v1[i\2+1], v1[i/2+1] + v1[i/2 - 1<<(valuation(i,2)-1) + 1])); v1
row1(n) = my(v1); v1 = [1]; forstep(i=if(n == 0, -1, logint(n, 2)), 0, -1, v1 = if(bittest(n, i), vector(#v1+1, j, v1[min(j, #v1)]), vector(#v1, j, sum(k=1, j, v1[k])))); v1
test1(n) = my(x = 'x, v1); v1 = upto1(n, x)/x; v1 = vector(n+1, i, Vec(v1[i])); v1 = vector(n\2+1, i, v1[2*i-1]) == vector(n\2+1, i, row1(i-1))
test2(n, m, q) = my(x = 'x, v1); v1 = upto1(n, x)/x; v1 = vector(n+1, i, Vecrev(v1[i])); v1 = vector(n+1, i, sum(j=1, #v1[i], a((-1 + 1<<(j-1)) << m + q)*v1[i][j]) == a((i-1) << m + q)); vecsum(v1) == (n+1)
Is there a way to prove it?
