Возможность свертки в рекурсии

[kthxbye]

Имеем последовательность

$$a(n)=(1+s(n))\cdot a(t(n)), a(0)=1$$

где $s(n)$ это A033264, а $t(n)$ это A053645. После небольшой инспекции отмечаем следующее:

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

и далее следуют формулы аналогичные последним четырем.

Можно ли во что-нибудь свернуть все это безобразие для $a(4n+2)$?

[kthxbye]

Банальное раскрытие дает

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

Последовательность $f(n)$

$$2,10,42,170,\cdots$$

есть в OEIS, это A020988. Указанные выше формулы и аналогичные им дают все значения $a(4n+2)$ кроме $a(f(n))=(n+1)!$. Скорее всего свертка возможна по аналогии с

$$a(2^{m}(2n+1))=a(2^{m}n) + a(2^{m-1}(2n+1)) + a(2^{m-1}(4n+1))$$

в

$$a(2n) = a(n) + a(n - 2^g(n)) + a(2n - 2^g(n))$$

для A329369 где $g(n)$ это A007814.

[kthxbye]

Введем функцию $\ell(n)$ аналогичную A053645

$$0,1,0,1,2,3,4,5,6,7,0,1,2,3,\cdots$$

где мы берем лишь подпоследовательности у которых длины это нечетные степени двойки.

$$\ell(n)=4\ell(n-1+\left\lfloor\frac{n \bmod 4}{2}\right\rfloor)+(n+2)\bmod 4, \ell(0)=0, \ell(1)=1$$

Затем вводим

$$\ell_{1}(n)=(1-[n=0])p(\ell(n))$$

где $p(n)$ это A001511. После этого переходим к

$$\ell_{2}(n)=(1-[n=0])f(\left\lfloor\frac{\ell_{1}(n)}{2}\right\rfloor+1)$$

где $f(n)$ это все также A020988 из предыдущего комментария. И наконец

$$a(4n+2)=[\ell(n)=0]\left(1+\frac{\log_{2}(\frac{3(4n+2)}{2}+1)}{2}\right)!+[\ell(n)>0]\left(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))$$

Формула не влазит, заканчивается

$$a(2^{\ell_{1}(n)+1}\left\lfloor\frac{4n+2-\ell_{2}(n)}{2^{\ell_{1}(n)+2}}\right\rfloor+\ell_{2}(n))$$

Кому интересно проверить, вот код на pari gp (буковки правда другие):

default(parisizemax,10^9)
n=15
l=vector(2^n,i,0)
for(i=2,2^n,l[i]=l[i\2]+1)
q=vector(2^n,i,0)
for(i=1,2^n,q[i]=gcd(2^20,i))
s=vector(2^n,i,0)
for(i=1,2^n,s[i]=if(q[i]==1,0,l[q[i]]))
a(n)=if(n==0,1,if(n%2==1,a(n\2),if(n%4==0,a(n\2),2*b(n\4))))
b(n)=if(n==0,1,if(n%2==1,2*b(n\2),3*c(n-1,1)))
c(n,k)=if(n==0,1,if(n%2==1,c(n\2,k),if(n%4==2,(k+2)*c(n\2-1,k),(k+3)*c(n\4-1,k+1))))
d=vector(2^n,i,0)
for(i=0,2^n-1,d[i+1]=a(i))
e=vector(2^n,i,0)
e[1]=0
e[2]=1
for(i=2,2^n-1,e[i+1]=4*e[i\4-1+(i%4)\2+1]+(i+2)%4)
f=vector(2^n,i,0)
for(i=0,2^n-1,f[i+1]=if(e[i+1]==0,0,s[e[i+1]]+1))
g=vector(2^n,i,0)
for(i=1,2^n,g[i]=2*(4^i-1)/3)
f1=vector(2^n,i,0)
for(i=0,2^n-1,f1[i+1]=if(e[i+1]==0,0,g[f[i+1]\2+1]))
h=vector(2^n,i,0)
for(i=0,2^n-1,h[i+1]=if(e[i+1]==0,0,2^(f[i+1]+1)*((4*i+2-f1[i+1])\2^(f[i+1]+2))+f1[i+1]))
j=vector(2^n,i,0)
j[1]=1
for(i=1,2^n-1,j[i+1]=if(i%2==1,j[i\2+1],if(i%4==0,j[i\2+1],if(e[i+1]==0,(l[3*i/2+1]/2+1)!,if(f[i\4+1]%2==1,1+(f[i\4+1]+1)/2,1)*j[h[i\4+1]+1]))))
print(sum(i=0,2^n-1,d[i+1]/j[i+1]))

[kthxbye]

В двух формулах ошибки:

$$\ell_{1}(n)=(1-[\ell(n)=0])p(\ell(n))$$

$$\ell_{2}(n)=(1-[\ell(n)=0])f(\left\lfloor\frac{\ell_{1}(n)}{2}\right\rfloor+1)$$

Код правильный.

Если, кстати, поменять $s(n)$ на A014081, то там похожая история:

$$a(4n+1)=a(2n)=a(n)$$

$$a(16n+11)=2a(4n+3), a(16n+19)=a(8n+11)$$

$$a(8n+7)=6b(n), a(16n+23)=3b'(n)$$

$$b'(2n)=b(n), b'(2n+1)=b'(n)$$

$$a(16n+15)=4c(n), a(32n+47)=4c'(n)$$

$$c'(2n)=c(n), c'(2n+1)=c'(n)$$

$$a(32n+31)=5d(n), a(64n+95)=5c'(n)$$

$$d'(2n)=d(n), d'(2n+1)=d'(n)$$

и далее аналогично последним 4-м формулам.