User:DroneBetter/H-trees g.f.'s

herein are my attempts at remediating the note

We have not found generating functions or explicit formulas for any of these sequences.

from the paper of recurrences for growth sequences in cellular automata (including H-trees)

I have had a few scattered and disorganised attempts at this in the past, that led to frustration

what they have left us

v₁(k) = { (0,1,3,5)[k] . . . . . . . . . . . . .k < 4(3*⌊log₂(k)⌋+1)*2^{⌊log₂(k)⌋-2}+1 . . . . .k = 2^{⌊log₂(k)⌋}3*2^{⌊log₂(k)⌋-1}+3 . . . . . . . . . . . .k = 2^{⌊log₂(k)⌋}+12*v₁(k-2^{⌊log₂(k)⌋})+v₁(k-2^{⌊log₂(k)⌋}+1)-1 . k = 2^{⌊log₂(k)⌋+1}-12*v₁(k-2^{⌊log₂(k)⌋})+v₁(k-2^{⌊log₂(k)⌋}+1) . . else

v1=lru_cache(λ k: (0,1,3,5)[k] if k<4 else (3*k.bit_length()-2<<k.bit_length()-3)+1 if not k&k-1 else 3*(2**(k.bit_length()-2)+1) if not k-1&k-2 else 2*v1(k-2**(k.bit_length()-1))+v1(k-2**(k.bit_length()-1)+1)-(not k&k+1))

let V_1,1(x)=x+3*x²+5*x³ and thereafter V_1,n(x)=(1+(1+x)*x²ⁿ)*V_1,n-1(x)+((3*n+1)*2^n-2*(1+x^2n-1)+(3*2^n-1-2)*x)*x²ⁿ, then gf(v₁) = V_1,∞

V1=λ n: polynomial(0,1,3,5) if n==1 else ((3*n+1)*2**(n-2)*(1+x**(2**n-1))+(3*2**(n-1)-2)*x)*x**2**n+(1+(1+2*x)*x**(2**n-1))*V1(n-1)

v₂(k) = { k . . . . . . . . . . . . . . . . . . k < 23*2^{⌊log₂(k)⌋}-1 . . . . . . . . . . . . .k = 2^{⌊log₂(k)⌋}v₂(k-2^{⌊log₂(k)⌋})+2*v₁(k-2^{⌊log₂(k)⌋}+1)-2 . k = 2^{⌊log₂(k)⌋+1}-1v₂(k-2^{⌊log₂(k)⌋})+2*v₁(k-2^{⌊log₂(k)⌋}+1) . . else

v2=λ k: k if k<2 else v2(i:=k-2**(k.bit_length()-1))+2*(v1(i+1)-(not k&k+1)) if k&k-1 else (3<<k.bit_length()-1)-1

v(k) = { k . . . . . . . . .k < 26*2^{⌊log₂(k)⌋}-4 . . . k = 2^{⌊log₂(k)⌋}4*v₂(k-2^{⌊log₂(k)⌋}) . else

v=λ k: k if k<2 else 4*v2(k-2**(k.bit_length()-1)) if k&k-1 else (6<<k.bit_length()-1)-4

external links

the paper in question:

• David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), p. 30-34