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

Author

N. J. A. Sloane, Feb 12 2003

Keywords

• nonn
• easy

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

Examples

			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
		

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

Crossrefs

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

Formula

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

Extensions

More terms from John W. Layman, Oct 29 2003

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