OFFSET
0,2
COMMENTS
Consider a few cellular automata with two states:
1. Cellular automaton used for definition of A102376 with rule: c(i,j) = ( c(i+1,j-1) + c(i+1,j+1) + c(i-1,j-1) + c(i-1,j+1) ) mod 2.
2. Cellular automaton with rule: c(i,j) = ( c(i+1,j) + c(i,j+1) + c(i-1,j) + c(i,j-1) ) mod 2.
3. Cellular automaton with rule: c(i,j) = 1 if ( c(i+1,j-1) + c(i+1,j+1) + c(i-1,j-1) + c(i-1,j+1) ) = 0 and ( c(i+1,j) + c(i,j+1) + c(i-1,j) + c(i,j-1) ) = 1; c(i,j) = 0 otherwise.
Consider a second-order cellular automaton with four states generated from a cellular automaton with two states above. If we start with a single cell with state 1 and all the others 0, then the number of nonzero states in subsequent steps will be the terms in the sequence.
The number of cells with state 1 forms A244643, denoted below as b(n). The number of cells with state 2 is b(n-1) with b(-1)=0; cells with state 3 may not appear for the given initial condition, so a(n) = b(n) + b(n-1).
LINKS
Alexander Yu. Vlasov, Table of n, a(n) for n = 0..10000
Alexander Yu. Vlasov, Snakes and fractals
Alexander Yu. Vlasov, Nine initial patterns
Alexander Yu. Vlasov, The sequence also describes number of replicators
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
EXAMPLE
a(4) = 21:
1
121
1 1 1
1212121
1 1 1
121
1
MATHEMATICA
msb[1]=1; msb[n_] := 2 msb[Quotient[n, 2]];
a[0] = 1; a[n_] := 4 a[n-msb[n]] + a[2 msb[n]-n-1];
Table[a[n], {n, 0, 64}]
PROG
(Axiom)
msb n == if n=1 then 1 else 2*msb(quo(n, 2))
a n == if n=0 then 1 else 4*a(n-msb(n))+a(2*msb(n)-n-1)
[a(n) for n in 0..64]
CROSSREFS
KEYWORD
nonn
AUTHOR
Alexander Yu. Vlasov, Jul 03 2014
STATUS
approved