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