A244642 Number of nonzero cells at n-th stage in some 2D reversible second-order cellular automata (see comments for precise definition).

1, 5, 9, 21, 25, 29, 41, 85, 89, 61, 65, 109, 121, 125, 169, 341, 345, 189, 161, 205, 209, 181, 225, 429, 441, 285, 289, 461, 505, 509, 681, 1365, 1369, 701, 545, 589, 561, 405, 449, 781, 785, 469, 441, 645, 689, 661, 865, 1709, 1721, 925, 769, 941, 945, 789, 961, 1805, 1849, 1181, 1185, 1869, 2041, 2045, 2729, 5461, 5465

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

a(0) = 1, a(2^k + j) = 4*a(j) + a(2^k - j - 1).

b(-1) = 0, b(0) = 1, b(2^k + j) = 4*b(j) + b(2^k - j - 2), a(n) = b(n) + b(n-1).

a(n) = A244643(n-1) + A244643(n) = A244643(2*n).

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

Cf. A102376, A147562, A244643.

Sequence in context: A273449 A297362 A175364 * A211424 A211428 A160720

Adjacent sequences: A244639 A244640 A244641 * A244643 A244644 A244645

Keyword

nonn

Author

Alexander Yu. Vlasov, Jul 03 2014

Status

approved