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

0, 1, 4, 5, 16, 9, 20, 21, 64, 25, 36, 29, 80, 41, 84, 85, 256, 89, 100, 61, 144, 65, 116, 109, 320, 121, 164, 125, 336, 169, 340, 341, 1024, 345, 356, 189, 400, 161, 244, 205, 576, 209, 260, 181, 464, 225, 436, 429, 1280, 441, 484, 285, 656, 289, 500, 461, 1344, 505, 676, 509, 1360, 681, 1364, 1365, 4096, 1369

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

Cf. A102376, A147562, A244642, A237711, A168081, A178590, A178568.

Sequence in context: A249113 A166590 A368739 * A085768 A166304 A078713

Adjacent sequences: A244640 A244641 A244642 * A244644 A244645 A244646

Keyword

nonn

Author

Alexander Yu. Vlasov, Jul 03 2014

Status

approved