%I
%S 0,1,5,9,21,25,37,49,85,89,101,113,149,161,197,233,341,345,357,369,
%T 405,417,453,489,597,609,645,681,789,825,933,1041,1365,1369,1381,1393,
%U 1429,1441,1477,1513,1621,1633,1669,1705,1813,1849,1957,2065,2389,2401,2437,2473
%N Number of "ON" cells at nth stage in the "UlamWarburton" twodimensional cellular automaton.
%C Studied by Holladay and Ulam circa 1960. See Fig. 1 and Example 1 of the Ulam reference.  _N. J. A. Sloane_, Aug 02 2009.
%C Singmaster calls this the UlamWarburton cellular automaton.  _N. J. A. Sloane_, Aug 05 2009
%C On the infinite square grid, start with all cells OFF.
%C Turn a single cell to the ON state.
%C At each subsequent step, each cell with exactly one neighbor ON is turned ON, and everything that is already ON remains ON.
%C Here "neighbor" refers to the four adjacent cells in the X and Y directions.
%C Note that "neighbor" could equally well refer to the four adjacent cells in the diagonal directions, since the graph formed by Z^2 with "onestep rook" adjacencies is isomorphic to Z^2 with "onestep bishop" adjacencies.
%C Also toothpick sequence starting with a central Xtoothpick followed by Ttoothpicks (see A160170 and A160172). The sequence gives the number of polytoothpicks in the structure after nth stage.  _Omar E. Pol_, Mar 28 2011
%C It appears that this sequence shares infinitely many terms with both A162795 and A169707, see Formula section and Example section.  _Omar E. Pol_, Feb 20 2015
%C It appears that the positive terms are also the odd terms (a bisection) of A151920.  _Omar E. Pol_, Mar 06 2015
%C Also, the number of active (ON,black) cells in the nth stage of growth of twodimensional cellular automaton defined by Wolfram's "Rule 558" or "Rule 686" based on the 5celled von Neumann neighborhood.  _Robert Price_, May 10 2016
%D D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 27.
%D S. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215224 of R. E. Bellman, ed., Mathematical Problems in the Biological Sciences, Proc. Sympos. Applied Math., Vol. 14, Amer. Math. Soc., 1962.
%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.
%H N. J. A. Sloane, <a href="/A147562/b147562.txt">Table of n, a(n) for n = 0..10000</a>
%H David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a>
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="http://neilsloane.com/doc/tooth.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n1)1) for n >= 2.]
%H Steven R. Finch, <a href="/A139250/a139250_1.pdf">Toothpicks and Live Cells</a>, July 21, 2015. [Cached copy, with permission of the author]
%H Bradley Klee, <a href="/A147562/a147562_1.png">Logperiodic coloring of the first quadrant, over the chair tiling</a>.
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polca003.jpg">Illustration of initial terms (Fig. 1: onestep rook  the current sequence)</a>, <a href="http://www.polprimos.com/imagenespub/polca005.jpg">(Fig. 2: onestep bishop)</a>, <a href="http://www.polprimos.com/imagenespub/polca007.jpg">(Fig. 3: overlapping squares)</a>, <a href="http://www.polprimos.com/imagenespub/polca009.jpg">(Fig. 4: overlapping Xtoothpicks)</a>, (2009), <a href="http://www.polprimos.com/imagenespub/polca033.jpg">(Fig. 5: overlapping circles)</a>, (2010)
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polca001.jpg">Illustration of initial terms of A139250, A160120, A147562 (overlapping figures)</a>, (2009).
%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="/A147562/a147562.png">Illustration of terms 0 through 9</a>
%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 Neil Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=_UtCli1SgjI">Terrific Toothpick Patterns</a>, Numberphile video (2018).
%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_5Neighbor_Cellular_Automata">Index to 2D 5Neighbor Cellular Automata</a>
%H <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>
%F For n>0, a(n) = 1 + 4*Sum_{k=1..n} 3^(wt(k1)1), where wt() = A000120().
%F From _Omar E. Pol_, Mar 13 2011: (Start)
%F a(n) = 2*A151917(n)  1, for n >= 1.
%F a(n) = 1 + 4*A151920(n2), for n >= 2.
%F (End)
%F It appears that a(n) = A162795(n) = A169707(n), if n is a member of A048645, otherwise a(n) < A162795(n) < A169707(n).  _Omar E. Pol_, Feb 20 2015
%F It appears that a(n) = A151920(2n2), n >= 1.  _Omar E. Pol_, Mar 06 2015
%F It appears that a(n) = (A130665(2n1)  1)/3, n >= 1.  _Omar E. Pol_, Mar 07 2015
%F a(n) = 1 + 4*(A130665(n1)  1)/3, n >= 1. _Omar E. Pol_, Mar 07 2015
%e If we label the generations of cells turned ON by consecutive numbers we get a rosetta cell pattern:
%e . . . . . . . . . . . . . . . . .
%e . . . . . . . . 4 . . . . . . . .
%e . . . . . . . 4 3 4 . . . . . . .
%e . . . . . . 4 . 2 . 4 . . . . . .
%e . . . . . 4 3 2 1 2 3 4 . . . . .
%e . . . . . . 4 . 2 . 4 . . . . . .
%e . . . . . . . 4 3 4 . . . . . . .
%e . . . . . . . . 4 . . . . . . . .
%e . . . . . . . . . . . . . . . . .
%e In the first generation, only the central "1" is ON, a(1)=1. In the next generation, we turn ON four "2", leading to a(2)=a(1)+4=5. In the third generation, four "3" are turned ON, a(3)=a(2)+4=9. In the fourth generation, each of the four wings allows three 4's to be turned ON, a(4)=a(3)+4*3=21.
%e From _Omar E. Pol_, Feb 18 2015: (Start)
%e Also, written as an irregular triangle T(j,k), j>=0, k>=1, in which the row lengths are the terms of A011782:
%e 1;
%e 5;
%e 9, 21;
%e 25, 37, 49, 85;
%e 89, 101,113,149,161,197,233,341;
%e 345,357,369,405,417,453,489,597,609,645,681,789,825,933,1041,1365;
%e ...
%e The right border gives the positive terms of A002450.
%e (End)
%e It appears that T(j,k) = A162795(j,k) = A169707(j,k), if k is a power of 2, for example: it appears that the three mentioned triangles only share the elements from the columns 1, 2, 4, 8, 16, ...  _Omar E. Pol_, Feb 20 2015
%p Since this is the partial sum sequence of A147582, it is most easily obtained using the Maple code given in A147582.
%p # [x,y] coordinates of cells on
%p Lse := [[0,0]] ;
%p # enclosing rectangle of the cells on (that is, minima and maxima in Lse)
%p xmin := 0 ;
%p xmax := 0 ;
%p ymin := 0 ;
%p ymax := 0 ;
%p # count neighbors of x,y which are on; return 0 if [x,y] is in L
%p cntnei := proc(x,y,L)
%p local a,p,xpt,ypt;
%p a := 0 ;
%p if not [x,y] in L then
%p for p in Lse do
%p xpt := op(1,p) ;
%p ypt := op(2,p) ;
%p if ( abs(xptx) = 1 and ypt=y ) or ( x=xpt and abs(ypty) = 1) then
%p a := a+1 ;
%p fi;
%p od:
%p fi:
%p RETURN(a) ;
%p end:
%p # loop over generations/steps
%p for stp from 1 to 10 do
%p Lnew := [] ;
%p for x from xmin1 to xmax+1 do
%p for y from ymin1 to ymax+1 do
%p if cntnei(x,y,Lse) = 1 then
%p Lnew := [op(Lnew),[x,y]] ;
%p fi;
%p od:
%p od:
%p for p in Lnew do
%p xpt := op(1,p) ;
%p ypt := op(2,p) ;
%p xmin := min(xmin,xpt) ;
%p xmax := max(xmax,xpt) ;
%p ymin := min(ymin,ypt) ;
%p ymax := max(ymax,ypt) ;
%p od:
%p Lse := [op(Lse),op(Lnew)] ;
%p print(nops(Lse)) ;
%t Map[Function[Apply[Plus,Flatten[ #1]]],CellularAutomaton[{686,{2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},200]] (* _Nadia Heninger_ and _N. J. A. Sloane_, Aug 11 2009 *)
%t ArrayPlot /@ CellularAutomaton[{686, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 16]
%Y Cf. A000120, A139250, A147582 (number turned ON at nth step), A147610, A130665, A151920, A160120, A160410, A160414, A151917, A160164, A162795, A169707, A187220, A246331.
%K nonn,nice,changed
%O 0,3
%A _N. J. A. Sloane_, based on emails from _Franklin T. AdamsWatters_, _R. J. Mathar_ and _David W. Wilson_, Apr 29 2009
%E Offset and initial terms changed by _N. J. A. Sloane_, Jun 07 2009
%E Numbers in the comment adapted to the offset by _R. J. Mathar_, Mar 03 2010
