Equivalence of sequences related to A033264

Question

• Let $a(n)$ be A033264 (i.e., number of blocks of $\{1,0\}$ in the binary expansion of $n$). Here $$ a(4n) = a(4n+1) = a(2n), \\ a(4n+2) = a(n)+1, \\ a(4n+3) = a(n), \\ a(0) = 0. $$
• Let $$ \ell(n) = \left\lfloor\log_2 n\right\rfloor. $$
• Let $b(n)$ be an integer sequence such that $$ b(n) = (1 + a(n))b(n-2^{\ell(n)}), \\ b(0) = 1. $$
• Let $c(n)$ be an integer sequence such that $$ c\left(\frac{2(4^n - 1)}{3}\right) = (n + 1)!, \\ c\left(2^{2m}(2k + 1) + \frac{2(4^m - 1)}{3}\right) = (m + 1)c\left(2^{2m}k + \frac{2(4^m - 1)}{3}\right), \\ c\left(2^{2m + 1}(2k + 1) + \frac{2(4^{m+1} - 1)}{3}\right) = c\left(2^{2m + 1}k + \frac{2(4^{m+1} - 1)}{3}\right), \\ c(0) = 1. $$

I conjecture that $$ c(n)=b(n). $$

Here is the PARI/GP program to check it numerically:

a(n) = if(n == 0, 0, if(n%4<2, a(n\2), a(n\4) + !(n%2)))
b(n) = if(n == 0, 1, (1 + a(n))*b(n - 1<<logint(n, 2)))
c(n) = my(A = 0, B = (n - 2*(4^A - 1)/3)/2^(2*A-1)); while(!(B == 0 || B%2 || valuation(B,2) == 1), A++; B = (n - 2*(4^A - 1)/3)/2^(2*A-1)); if(B == 0, (A+1)!, if(B%2, c(2^(2*(A-1))*(B-1) + 2*(4^A - 1)/3), (A+1)*c(2^(2*A-1)*(B-1) + 2*(4^A - 1)/3)))
test(n) = c(n) == b(n)

Is there a way to prove it?

Answer 1

Given the structure of these sequences, it seems convenient to describe them as integer valued functions of binary strings rather than of natural numbers. This way, the recursions from $b$ and $c$ appear to be recursive ways of computing a quantity of a string $x$, starting from the left, resp. from the right.

Specifically, for a binary string $x:=x_r\dots x_1x_0$ of finite length $r>0$ and $m=\sum_{i=0}^rx_i2^i$, we write $f(x)$ instead of $f(m)$ for $f\in\{a,b,c\}.$ Then the recursions translate into: $$ a(x00)=a(x01)=a(x0) ,\\ a(x10)=a(x)+1,\\ a(x11)=a(x)=a(0x),\\ a(0)=0; $$

$$ b(1x)=\big(1+a(1x)\big)b(x),\\ b(0)=1. $$

In the equations for $c$, it is convenient to write $$2^{2m+1}(2k+1)+\frac23(4^{m+1}-1)=$$$$=2^{2m+2}(k+1)+\frac23(4^m-1),$$ and $$2^{2m+1}k+\frac23(4^{m+1}-1)=$$$$= 2^{2m+1}(k+1)+\frac23(4^m-1),$$ so that there is nothing to be carried in the binary representation of the sum. Thus

$$ c((10)^n)=(n+1)!,\\ c(x1(10)^n)=(n+1)c(x(10)^n),\\ c(x00(10)^n)=c(x0(10)^n),\\ c(0)=1. $$ Finally, we may add to these $f(0x)=f(x)$ for $f\in\{a,b,c\},$ since the value of $f(x)$ only depends on the numerical value of the string.

Note that $a(x11)=a(x)$ and $a(x01)=a(x0)$ together imply $a(x1^{2p})=a(x)$ and $a(x01^{2p+1})=a(x0)$, so that in the argument of $a$, every initial block of $1$’s on the right can be removed, and in particular $a(x1)=a(x)$.

The analogous relation $b(x1)=b(x)$ then follows by induction, since it is true for $x=0$. Also, $c(x1)=c(x)$ for $c$ is a particular case of the second equation for $c$, with $n=0$. Therefore for the sake of notation we may and do prove the equality $b(x)=c(x)$ for binary strings of odd numbers.

Every such string $x$ (after dropping initial $0$’s from the left), can be written uniquely as $$x=1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0},$$ with $n\ge1$ and positive integer exponents $q_i,$ $p_i$.

In this notation, $a(x)=n$, the number of blocks of $0$’s. It then immediately follows by induction that

$$ b(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i}.$$

Using the relations for $c$, we can reduce the computation of $c(x)$ to the known value $c((10)^n)=(n+1)!$, extracting in order from the right to the left (i.e. for $i$ from $0$ to $n$) all $0$’s but one from the block $0^{p_i}$, with no effect on the value of $c$, and all $1$’s but one from the block $1^{q_i}$, multiplying by a factor $(1+i)^{p_i}$. In conclusion $$ c(1^{p_n}0^{q_n}\dots 1^{p_1}0^{q_1}1^{p_0})=\prod_{i=1}^n(1+i)^{p_i},$$ as we wished to prove.