login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 24
1, 5, 5, 17, 5, 25, 17, 61, 5, 25, 25, 85, 17, 85, 61, 217, 5, 25, 25, 85, 25, 125, 85, 305, 17, 85, 85, 289, 61, 305, 217, 773, 5, 25, 25, 85, 25, 125, 85, 305, 25, 125, 125, 425, 85, 425, 305, 1085, 17, 85, 85, 289, 85, 425, 289, 1037, 61, 305, 305, 1037, 217, 1085, 773, 2753 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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]

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

This is the Run Length Transform of A007483. - N. J. A. Sloane, Aug 25 2014

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

The partial sums are in A253908, in which the structure looks like an irregular step pyramid. - Omar E. Pol, Jan 29 2015

Rules 518, 550 and 582 also generate this sequence. - Robert Price, Mar 01 2016

REFERENCES

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170-179.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..8192

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata

Shalosh B. Ekhad, N. J. A. Sloane, and  Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796, 2015; see also the Accompanying Maple Package.

Shalosh B. Ekhad, N. J. A. Sloane, and  Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249, 2015.

N. H. Packard and S. Wolfram, Two-Dimensional Cellular Automata, Journal of Statistical Physics, 38 (1985), 901-946.

N. J. A. Sloane, Illustration of first 15 generations

N. J. A. Sloane, Illustration of first 28 generations

N. J. A. Sloane, Illustration for a(15)=217

N. J. A. Sloane, Illustration for a(31)=773

N. J. A. Sloane, Illustration for a(63)=2753

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168, 2015

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: Part 1, Part 2

Eric Weisstein's World of Mathematics, Elementary Cellular Automaton

S. Wolfram, A New Kind of Science

Index to 2D 5-Neighbor Cellular Automata

Index to Elementary Cellular Automata

Index entries for sequences related to cellular automata

FORMULA

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

EXAMPLE

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

......................0

.............0.......000

.......0............0...0

.0....000..0.0.0...00.0.00

.......0............0...0

.............0.......000

......................0

From Omar E. Pol, Jan 29 2015: (Start)

May be arranged into blocks of sizes A011782:

1;

5;

5,17;

5,25,17,61;

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

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

5,25,25,85,25,125,85,305,25,125,125,425,85,425,305,1085,17,85,85,289,85,425,289,1037,61,305,305,1037,217,1085,773,2753;

So the right border gives A007483.

(End)

From Omar E. Pol, Mar 19 2015: (Start)

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

1;

..

5;

..

5;

17;

..........

5,     25;

17;

61;

.....................

5,     25,  25,   85;

17,    85;

61;

217;

..........................................

5,     25,  25,   85,  25, 125,  85,  305;

17,    85,  85,  289;

61,   305;

217;

773;

.................................................................................

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

17,    85,  85,  289,  85, 425, 289, 1037;

61,   305, 305, 1037;

217, 1085;

773;

2753;

...

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

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

(End)

MAPLE

# Maple code from N. J. A. Sloane, Aug 20 2014:

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

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

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

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

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

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

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

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

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

end;

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

OddCA(f, 100);

MATHEMATICA

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

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

CROSSREFS

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

See A253090 for 9-celled neighborhood version.

Sequence in context: A194615 A195465 A173464 * A273502 A273606 A273544

Adjacent sequences:  A072269 A072270 A072271 * A072273 A072274 A072275

KEYWORD

nonn,nice

AUTHOR

Miklos Kristof, Jul 09 2002

EXTENSIONS

Extended and edited by John W. Layman, Jul 17 2002

Minor edits by N. J. A. Sloane, Jan 07 2010

More terms from N. J. A. Sloane, Apr 17 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 00:50 EDT 2018. Contains 316252 sequences. (Running on oeis4.)