%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