OFFSET
-1,3
COMMENTS
Consider cellular automata with two states defined in A244642 and second order cellular automata with four states generated from them. If we start with a single cell with state 1 and all the others 0, then number cells with state 1 in subsequent steps will be the terms in the sequence a(n). Number of cells with state 2 is a(n-1), where a(-1) = 0.
Equals row 4 in the array shown in A178568.
LINKS
Alexander Yu. Vlasov, Table of n, a(n) for n = -1..10000
Alexander Yu. Vlasov, Snakes and fractals
Alexander Yu. Vlasov, Nine initial patterns
Alexander Yu. Vlasov, On number of nonzero cells in some two-dimensional reversible second-order cellular automata, arXiv:1407.6553 [math.CO], 2014.
Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 13.
FORMULA
a(-1) = 0, a(0) = 1, a(2^k + j) = 4*a(j) + a(2^k - j - 2).
a(n-1)+a(n) = A244642(n).
a(2n+1) = 4a(n), a(2n+2) = a(n+1) + a(n).
G.f.: Product_{k>=0} (1 + 4*x^(2^k) + x^(2^(k+1))). - Ilya Gutkovskiy, Mar 16 2021
EXAMPLE
For n=4, a(4) = 16 and a(n-1) = a(3) = 5.
....1
...121
..1.1.1
.1212121
..1.1.1
...121
....1
MATHEMATICA
msb[1]=1; msb[n_] := 2 msb[Quotient[n, 2]];
a[-1] = 0; a[0] = 1; a[n_] := 4 a[n-msb[n]] + a[2 msb[n]-n-2];
Table[a[n], {n, -1, 64}] (* recursion *)
Table[PolynomialMod[Fibonacci[n, f]/.f->(x+1/x+y+1/y), 2], {n, 0, 24}]/.{x->1, y->1} (* calculation using GF(2) polynomial representation of CA *)
PROG
(Axiom)
msb n == if n=1 then 1 else 2*msb(quo(n, 2))
a n == if n<1 then n+1 else 4*a(n-msb(n))+a(2*msb(n)-n-2)
[a(n) for n in -1..64]
CROSSREFS
KEYWORD
nonn
AUTHOR
Alexander Yu. Vlasov, Jul 03 2014
STATUS
approved