cp's OEIS Frontend

A072272 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.

%I A072272 #110 Feb 16 2025 08:32:46
%S A072272 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 A072272 17,85,85,289,61,305,217,773,5,25,25,85,25,125,85,305,25,125,125,425,
%U A072272 85,425,305,1085,17,85,85,289,85,425,289,1037,61,305,305,1037,217,1085,773,2753
%N A072272 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 A072272 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 A072272 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 A072272 This is the Run Length Transform of A007483. - _N. J. A. Sloane_, Aug 25 2014
%C A072272 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 A072272 The partial sums are in A253908, in which the structure looks like an irregular stepped pyramid. - _Omar E. Pol_, Jan 29 2015
%C A072272 Rules 518, 550 and 582 also generate this sequence. - _Robert Price_, Mar 01 2016
%D A072272 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; pp. 170-179.
%H A072272 Alois P. Heinz, <a href="/A072272/b072272.txt">Table of n, a(n) for n = 0..8192</a>
%H A072272 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 A072272 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 A072272 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 A072272 Nathan Epstein, <a href="https://giant.gfycat.com/GreatGrippingHyracotherium.webm">Animation of CA generating A072272</a>.
%H A072272 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 A072272 N. J. A. Sloane, <a href="/A072272/a072272.png">Illustration of first 15 generations</a>.
%H A072272 N. J. A. Sloane, <a href="/A072272/a072272_1.png">Illustration of first 28 generations</a>.
%H A072272 N. J. A. Sloane, <a href="/A072272/a072272_2.png">Illustration for a(15)=217</a>.
%H A072272 N. J. A. Sloane, <a href="/A072272/a072272_3.png">Illustration for a(31)=773</a>.
%H A072272 N. J. A. Sloane, <a href="/A072272/a072272_4.png">Illustration for a(63)=2753</a>.
%H A072272 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 A072272 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 A072272 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 A072272 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>.
%H A072272 S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>.
%H A072272 <a href="https://oeis.org/wiki/Index_to_2D_5-Neighbor_Cellular_Automata">Index to 2D 5-Neighbor Cellular Automata</a>
%H A072272 <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>
%H A072272 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F A072272 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 A072272 To illustrate a(0) = 1, a(1) = 5, a(2) = 5, a(3) = 17:
%e A072272   ......................0
%e A072272   .............0.......000
%e A072272   .......0............0...0
%e A072272   .0....000..0.0.0...00.0.00
%e A072272   .......0............0...0
%e A072272   .............0.......000
%e A072272   ......................0
%e A072272 From _Omar E. Pol_, Jan 29 2015: (Start)
%e A072272 May be arranged into blocks of sizes A011782:
%e A072272   1;
%e A072272   5;
%e A072272   5,17;
%e A072272   5,25,17,61;
%e A072272   5,25,25,85,17,85,61,217;
%e A072272   5,25,25,85,25,125,85,305,17,85,85,289,61,305,217,773;
%e A072272   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 A072272     61,305,305,1037,217,1085,773,2753;
%e A072272 So the right border gives A007483.
%e A072272 (End)
%e A072272 From _Omar E. Pol_, Mar 19 2015: (Start)
%e A072272 Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:
%e A072272      1;
%e A072272   .....
%e A072272      5;
%e A072272   .....
%e A072272      5;
%e A072272     17;
%e A072272   ...........
%e A072272      5,   25;
%e A072272     17;
%e A072272     61;
%e A072272   ......................
%e A072272      5,   25,  25,   85;
%e A072272     17,   85;
%e A072272     61;
%e A072272    217;
%e A072272   ...........................................
%e A072272      5,   25,  25,   85,  25, 125,  85,  305;
%e A072272     17,   85,  85,  289;
%e A072272     61,  305;
%e A072272    217;
%e A072272    773;
%e A072272   ..................................................................................
%e A072272      5,   25,  25,   85,  25, 125,  85,  305, 25, 125, 125, 425, 85, 425, 305, 1085;
%e A072272     17,   85,  85,  289,  85, 425, 289, 1037;
%e A072272     61,  305, 305, 1037;
%e A072272    217, 1085;
%e A072272    773;
%e A072272   2753;
%e A072272   ...
%e A072272 Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k).
%e A072272 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 A072272 (End)
%p A072272 C:=f->subs({x=1,y=1},f);
%p A072272 # Find number of ON cells in CA for generations 0 thru M defined by rule
%p A072272 # that cell is ON iff number of ON cells in nbd at time n-1 was odd
%p A072272 # where nbd is defined by a polynomial or Laurent series f(x,y).
%p A072272 OddCA:=proc(f,M) global C; local n,a,i,f2,g,p;
%p A072272 f2:=simplify(expand(f)) mod 2;
%p A072272 a:=[]; p:=1; g:=f2;
%p A072272 for n from 0 to M do a:=[op(a),C(p)]; p:=expand(p*f2) mod 2; od:
%p A072272 lprint([seq(a[i],i=1..nops(a))]);
%p A072272 end;
%p A072272 f:=1+1/x+x+1/y+y;
%p A072272 OddCA(f,100);
%p A072272 # _N. J. A. Sloane_, Aug 20 2014
%t A072272 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 A072272 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 A072272 Cf. A048883, A170878 (first differences), A253908 (partial sums).
%Y A072272 See A253090 for 9-celled neighborhood version.
%K A072272 nonn,nice
%O A072272 0,2
%A A072272 _Miklos Kristof_, Jul 09 2002
%E A072272 Extended and edited by _John W. Layman_, Jul 17 2002
%E A072272 Minor edits by _N. J. A. Sloane_, Jan 07 2010
%E A072272 More terms from _N. J. A. Sloane_, Apr 17 2010