The possibility of convolution in recursion

74 Views Asked by At

We have a sequence $$a(n)=(1+s(n))\cdot a(t(n)), a(0)=1$$ where $s(n)$ is A033264 and $t(n)$ is A053645. After a short inspection, we note the following: $$a(2n+1)=a(n), a(4n)=a(2n), a(4n+2)=2b(n), a(0)=1$$$$b(2n+1)=2b(n), b(2n)=3c(n-1), b(0)=1$$$$c(2n+1)=c(n), c(4n+2)=3c(2n), c(4n)=4d(n-1), c(0)=1$$$$d(2n+1)=d(n), d(4n+2)=4d(2n), d(4n)=5e(n-1), d(0)=1$$$$e(2n+1)=e(n), e(4n+2)=5e(2n), e(4n)=6f(n-1), e(0)=1$$$$f(2n+1)=f(n), f(4n+2)=6f(2n), f(4n)=7g(n-1), f(0)=1$$ and then there are formulas similar to the last four.

Is it possible to collapse all this ugliness into something?

1

There are 1 best solutions below

0
On

We got $$a(2^{2}(2n+1)+2)=2a(4n+2)$$$$a(2^{3}(2n+1)+10)=a(8n+10)$$$$a(2^{4}(2n+1)+10)=3a(16n+10)$$$$a(2^{5}(2n+1)+42)=a(32n+42)$$$$a(2^{6}(2n+1)+42)=4a(64n+42)$$$$a(2^{7}(2n+1)+170)=a(128n+170)$$ where $f(n)$ $$2,10,42,170,\cdots$$ is A020988. The above formulas and similar ones give all the values of $a (4n+2)$ except $a(f(n))=(n+1)!$.

Let's introduce a function $\ell (n)$ similar to A053645 $$0,1,0,1,2,3,4,5,6,7,0,1,2,3,\cdots$$ where we take only subsequences whose lengths are odd powers of two. $$\ell(n)=4\ell(\left\lfloor\frac{n}{4}\right\rfloor-1+\left\lfloor\frac{n \bmod 4}{2}\right\rfloor)+(n+2)\bmod 4, \ell(0)=0, \ell(1)=1$$ Then we set $$\ell_{1}(n)=(1-[\ell(n)=0])p(\ell(n))$$ where $p(n)$ is A001511. After that, we set $$\ell_{2}(n)=(1-[\ell(n)=0])f(\left\lfloor\frac{\ell_{1}(n)}{2}\right\rfloor+1)$$ And finally $$a(4n+2)=[\ell(n)=0]\left(2+\frac{\log_{2}(\frac{3n}{2}+1)}{2}\right)!+[\ell(n)>0]\left(1+ (\ell_{1}(n)\bmod 2)\frac{\ell_{1}(n)+1}{2}\right)a(2^{\ell_{1}(n)+1}\left\lfloor\frac{4n+2-\ell_{2}(n)}{2^{\ell_{1}(n)+2}}\right\rfloor+\ell_{2}(n))$$ Who is interested to check, here is the code for pari gp.