A079317 - OEIS

%I #26 Jul 26 2024 21:16:31

%S 1,5,5,17,9,29,21,65,25,77,37,113,49,149,85,257,89,269,101,305,113,

%T 341,149,449,161,485,197,593,233,701,341,1025,345,1037,357,1073,369,

%U 1109,405,1217,417,1253,453,1361,489,1469,597,1793,609,1829,645,1937,681

%N 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.

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

%C 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.

%C 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

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

%C 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

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

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

%H Robert Price, <a href="/A079317/b079317.txt">Table of n, a(n) for n = 0..128</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 Robert Price, <a href="/A079317/a079317.tmp.txt">Diagrams of the first 20 stages</a>

%H D. Singmaster, <a href="/A079314/a079314.pdf">On the cellular automaton of Ulam and Warburton</a>, 2003 [Cached copy, included with permission]

%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 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="/index/Ce#cell">Index entries for sequences related to cellular automata</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>

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

%e Generations 1 through 4 (X = ON):

%e ..................X

%e ..........X......XXX

%e ....X...........X...X

%e X..XXX..X.X.X..XX.X.XX

%e ....X...........X...X

%e ..........X......XXX

%e ..................X

%e ...........Sizes of first 20 generations:.........

%e .........n...OFF->ON...ON->OFF..Net gain..Total ON

%e .........n...A079315.(A147582)...A151921...A079317

%e --------------------------------------------------

%e .........0.........0.........0.........0.........0

%e .........1.........1.........0.........1.........1

%e .........2.........4.........0.........4.........5

%e .........3.........4.........4.........0.........5

%e .........4........12.........0........12........17

%e .........5.........4........12........-8.........9

%e .........6........20.........0........20........29

%e .........7........12........20........-8........21

%e .........8........44.........0........44........65

%e .........9.........4........44.......-40........25

%e ........10........52.........0........52........77

%e ........11........12........52.......-40........37

%e ........12........76.........0........76.......113

%e ........13........12........76.......-64........49

%e ........14.......100.........0.......100.......149

%e ........15........36.......100.......-64........85

%e ........16.......172.........0.......172.......257

%e ........17.........4.......172......-168........89

%e ........18.......180.........0.......180.......269

%e ........19........12.......180......-168.......101

%e ........20.......204.........0.......204.......305

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

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_, Feb 12 2003

%E More terms from _John W. Layman_, Oct 29 2003

%E Edited by _N. J. A. Sloane_, Aug 05 2009