A079317 Number of ON cells after n generations of cellular automaton on square grid in which cells which share exactly one edge with an ON cell change their state.

1, 5, 5, 17, 9, 29, 21, 65, 25, 77, 37, 113, 49, 149, 85, 257, 89, 269, 101, 305, 113, 341, 149, 449, 161, 485, 197, 593, 233, 701, 341, 1025, 345, 1037, 357, 1073, 369, 1109, 405, 1217, 417, 1253, 453, 1361, 489, 1469, 597, 1793, 609, 1829, 645, 1937, 681

Offset

0,2

Comments

We work on the square grid in which each cell has four neighbors.

Start with cell (0,0) ON and all other cells OFF; at each succeeding stage the cells that share exactly one edge with an ON cell change their state.

This is not the CA discussed by Singmaster in the reference given in A079314. That was an error based on my misreading of the paper. - N. J. A. Sloane, Aug 05 2009

If cells never turn OFF we get the CA of A147562.

The number of active (ON, black) cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 678", based on the 5-celled von Neumann neighborhood. - Robert Price, May 21 2016

References

D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.

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

Links

Robert Price, Table of n, a(n) for n = 0..128

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, 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.]

Robert Price, Diagrams of the first 20 stages

D. Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]

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 [math.CO], 2015

Eric Weisstein's World of Mathematics, Elementary Cellular Automaton

S. Wolfram, A New Kind of Science

Index entries for sequences related to cellular automata

Index to 2D 5-Neighbor Cellular Automata

Index to Elementary Cellular Automata

Formula

a(n) = a(n-1) + A151921(n) (and we have an explicit formula for A151921).

Example

Generations 1 through 4 (X = ON):
..................X
..........X......XXX
....X...........X...X
X..XXX..X.X.X..XX.X.XX
....X...........X...X
..........X......XXX
..................X
...........Sizes of first 20 generations:.........
.........n...OFF->ON...ON->OFF..Net gain..Total ON
.........n...A079315.(A147582)...A151921...A079317
--------------------------------------------------
.........0.........0.........0.........0.........0
.........1.........1.........0.........1.........1
.........2.........4.........0.........4.........5
.........3.........4.........4.........0.........5
.........4........12.........0........12........17
.........5.........4........12........-8.........9
.........6........20.........0........20........29
.........7........12........20........-8........21
.........8........44.........0........44........65
.........9.........4........44.......-40........25
........10........52.........0........52........77
........11........12........52.......-40........37
........12........76.........0........76.......113
........13........12........76.......-64........49
........14.......100.........0.......100.......149
........15........36.......100.......-64........85
........16.......172.........0.......172.......257
........17.........4.......172......-168........89
........18.......180.........0.......180.......269
........19........12.......180......-168.......101
........20.......204.........0.......204.......305

Crossrefs

Cf. A079315 gives number which change from OFF to ON at generation n, A151921 gives net gain in number of ON cells.

Sequence in context: A273758 A273835 A246333 * A273482 A273792 A273855

Adjacent sequences: A079314 A079315 A079316 * A079318 A079319 A079320

Keyword

nonn,easy

Author

N. J. A. Sloane, Feb 12 2003

Extensions

More terms from John W. Layman, Oct 29 2003

Edited by N. J. A. Sloane, Aug 05 2009

Status

approved