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

%I #50 Jan 14 2024 07:19:38

%S 0,1,4,5,16,9,20,21,64,25,36,29,80,41,84,85,256,89,100,61,144,65,116,

%T 109,320,121,164,125,336,169,340,341,1024,345,356,189,400,161,244,205,

%U 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

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

%C 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.

%C Equals row 4 in the array shown in A178568.

%H Alexander Yu. Vlasov, <a href="/A244643/b244643.txt">Table of n, a(n) for n = -1..10000</a>

%H Alexander Yu. Vlasov, <a href="http://ayvlasov.wordpress.com/2014/06/28/snakes-and-fractals/">Snakes and fractals</a>

%H Alexander Yu. Vlasov, <a href="https://ayvlasov.files.wordpress.com/2014/06/simplser.png">Nine initial patterns</a>

%H Alexander Yu. Vlasov, <a href="http://arxiv.org/abs/1407.6553">On number of nonzero cells in some two-dimensional reversible second-order cellular automata</a>, arXiv:1407.6553 [math.CO], 2014.

%H Alexander Yu. Vlasov, <a href="https://arxiv.org/abs/2312.13034">Modelling reliability of reversible circuits with 2D second-order cellular automata</a>, arXiv:2312.13034 [nlin.CG], 2023. See page 13.

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

%F a(n-1)+a(n) = A244642(n).

%F a(2n+1) = 4a(n), a(2n+2) = a(n+1) + a(n).

%F G.f.: Product_{k>=0} (1 + 4*x^(2^k) + x^(2^(k+1))). - _Ilya Gutkovskiy_, Mar 16 2021

%e For n=4, a(4) = 16 and a(n-1) = a(3) = 5.

%e ....1

%e ...121

%e ..1.1.1

%e .1212121

%e ..1.1.1

%e ...121

%e ....1

%t msb[1]=1; msb[n_] := 2 msb[Quotient[n,2]];

%t a[-1] = 0; a[0] = 1; a[n_] := 4 a[n-msb[n]] + a[2 msb[n]-n-2];

%t Table[a[n], {n, -1, 64}] (* recursion *)

%t 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 *)

%o (Axiom)

%o msb n == if n=1 then 1 else 2*msb(quo(n,2))

%o a n == if n<1 then n+1 else 4*a(n-msb(n))+a(2*msb(n)-n-2)

%o [a(n) for n in -1..64]

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

%K nonn

%O -1,3

%A _Alexander Yu. Vlasov_, Jul 03 2014