login
Number of active cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 614", based on the 5-celled von Neumann neighborhood.
25

%I #109 Aug 27 2023 19:46:46

%S 1,5,5,17,5,25,17,61,5,25,25,85,17,85,61,217,5,25,25,85,25,125,85,305,

%T 17,85,85,289,61,305,217,773,5,25,25,85,25,125,85,305,25,125,125,425,

%U 85,425,305,1085,17,85,85,289,85,425,289,1037,61,305,305,1037,217,1085,773,2753

%N Number of active cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 614", based on the 5-celled von Neumann neighborhood.

%C Consider only the four nearest (N,S,E,W) neighbors of a cell together with the cell itself. In the next state, the state of a cell will change if an odd number of these five cells is ON. [Comment corrected by _N. J. A. Sloane_, Aug 25 2014]

%C Equivalently, a(n) is the number of ON cells at generation n of 2-D CA defined as follows: the neighborhood of a cell consists of the cell itself and the four adjacent E, W, N, S cells. A cell is ON iff an odd number of these cells was ON at the previous generation. - _N. J. A. Sloane_, Aug 20 2014. This is the odd-rule cellular automaton defined by OddRule 057 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link).

%C This is the Run Length Transform of A007483. - _N. J. A. Sloane_, Aug 25 2014

%C The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - _N. J. A. Sloane_, Aug 25 2014

%C The partial sums are in A253908, in which the structure looks like an irregular stepped pyramid. - _Omar E. Pol_, Jan 29 2015

%C Rules 518, 550 and 582 also generate this sequence. - _Robert Price_, Mar 01 2016

%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; pp. 170-179.

%H Alois P. Heinz, <a href="/A072272/b072272.txt">Table of n, a(n) for n = 0..8192</a>

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]

%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.01796">A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata</a>, arXiv:1503.01796 [math.CO], 2015; see also the <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/CAcount.html">Accompanying Maple Package</a>.

%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.04249">Odd-Rule Cellular Automata on the Square Grid</a>, arXiv:1503.04249 [math.CO], 2015.

%H Nathan Epstein, <a href="https://giant.gfycat.com/GreatGrippingHyracotherium.webm">Animation of CA generating A072272</a>.

%H N. H. Packard and S. Wolfram, <a href="http://new.math.uiuc.edu/im2008/dakkak/papers/files/wolfram.2dca.pdf">Two-Dimensional Cellular Automata</a>, Journal of Statistical Physics, 38 (1985), 901-946.

%H N. J. A. Sloane, <a href="/A072272/a072272.png">Illustration of first 15 generations</a>.

%H N. J. A. Sloane, <a href="/A072272/a072272_1.png">Illustration of first 28 generations</a>.

%H N. J. A. Sloane, <a href="/A072272/a072272_2.png">Illustration for a(15)=217</a>.

%H N. J. A. Sloane, <a href="/A072272/a072272_3.png">Illustration for a(31)=773</a>.

%H N. J. A. Sloane, <a href="/A072272/a072272_4.png">Illustration for a(63)=2753</a>.

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>.

%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.

%H N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: <a href="https://vimeo.com/119073818">Part 1</a>, <a href="https://vimeo.com/119073819">Part 2</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>.

%H S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>.

%H <a href="https://oeis.org/wiki/Index_to_2D_5-Neighbor_Cellular_Automata">Index to 2D 5-Neighbor Cellular Automata</a>

%H <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%F a(0)=1; thereafter a(2t)=a(t), a(4t+1)=5*a(t), a(4t+3)=3*a(2t+1)+2*a(t). - _N. J. A. Sloane_, Jan 26 2015

%e To illustrate a(0) = 1, a(1) = 5, a(2) = 5, a(3) = 17:

%e ......................0

%e .............0.......000

%e .......0............0...0

%e .0....000..0.0.0...00.0.00

%e .......0............0...0

%e .............0.......000

%e ......................0

%e From _Omar E. Pol_, Jan 29 2015: (Start)

%e May be arranged into blocks of sizes A011782:

%e 1;

%e 5;

%e 5,17;

%e 5,25,17,61;

%e 5,25,25,85,17,85,61,217;

%e 5,25,25,85,25,125,85,305,17,85,85,289,61,305,217,773;

%e 5,25,25,85,25,125,85,305,25,125,125,425,85,425,305,1085,17,85,85,289,85,425,289,1037,

%e 61,305,305,1037,217,1085,773,2753;

%e So the right border gives A007483.

%e (End)

%e From _Omar E. Pol_, Mar 19 2015: (Start)

%e Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:

%e 1;

%e .....

%e 5;

%e .....

%e 5;

%e 17;

%e ...........

%e 5, 25;

%e 17;

%e 61;

%e ......................

%e 5, 25, 25, 85;

%e 17, 85;

%e 61;

%e 217;

%e ...........................................

%e 5, 25, 25, 85, 25, 125, 85, 305;

%e 17, 85, 85, 289;

%e 61, 305;

%e 217;

%e 773;

%e ..................................................................................

%e 5, 25, 25, 85, 25, 125, 85, 305, 25, 125, 125, 425, 85, 425, 305, 1085;

%e 17, 85, 85, 289, 85, 425, 289, 1037;

%e 61, 305, 305, 1037;

%e 217, 1085;

%e 773;

%e 2753;

%e ...

%e Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k).

%e It appears that the configuration of ON cells of T(s,r,k) is of the same kind as the configuration of ON cells of T(s+1,r,k).

%e (End)

%p C:=f->subs({x=1,y=1},f);

%p # Find number of ON cells in CA for generations 0 thru M defined by rule

%p # that cell is ON iff number of ON cells in nbd at time n-1 was odd

%p # where nbd is defined by a polynomial or Laurent series f(x,y).

%p OddCA:=proc(f,M) global C; local n,a,i,f2,g,p;

%p f2:=simplify(expand(f)) mod 2;

%p a:=[]; p:=1; g:=f2;

%p for n from 0 to M do a:=[op(a),C(p)]; p:=expand(p*f2) mod 2; od:

%p lprint([seq(a[i],i=1..nops(a))]);

%p end;

%p f:=1+1/x+x+1/y+y;

%p OddCA(f,100);

%p # _N. J. A. Sloane_, Aug 20 2014

%t Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[{ 614, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},100]] (* _N. J. A. Sloane_, Apr 17 2010 *)

%t ArrayPlot /@ CellularAutomaton[{ 614, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},6] (* _N. J. A. Sloane_, Aug 25 2014 *)

%Y Cf. A048883, A170878 (first differences), A253908 (partial sums).

%Y See A253090 for 9-celled neighborhood version.

%K nonn,nice

%O 0,2

%A _Miklos Kristof_, Jul 09 2002

%E Extended and edited by _John W. Layman_, Jul 17 2002

%E Minor edits by _N. J. A. Sloane_, Jan 07 2010

%E More terms from _N. J. A. Sloane_, Apr 17 2010