|
%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 n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).
%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 Ulam-Warburton 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 "one-step rook" adjacencies is isomorphic to Z^2 with "one-step bishop" adjacencies.
%C Also toothpick sequence starting with a central X-toothpick followed by T-toothpicks (see A160170 and A160172). The sequence gives the number of polytoothpicks in the structure after n-th stage. - Omar E. Pol, Mar 28 2011
%D D. Singmaster, On the cellular automaton of Ulam and Warburton, unpublished manuscript, 2003.
%D S. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215-224 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, 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), 157-191
%H David Applegate, <a href="http://www.research.att.com/~david/oeis/toothpick.html">The movie version</a>
%H O. E. Pol, <a href="http://www.polprimos.com/imagenespub/polca003.jpg">Illustration of initial terms (one-step rook - the current sequence)</a> [From _Omar E. Pol_, Nov 02 2009]
%H O. E. Pol, <a href="http://www.polprimos.com/imagenespub/polca005.jpg">Illustration of initial terms (one-step bishop)</a> [From _Omar E. Pol_, Nov 02 2009]
%H O. E. Pol, <a href="http://www.polprimos.com/imagenespub/polca007.jpg">Illustration of initial terms (overlapping squares)</a> [From _Omar E. Pol_, Nov 02 2009]
%H O. E. Pol, <a href="http://www.polprimos.com/imagenespub/polca009.jpg">Illustration of initial terms (overlapping X-toothpicks)</a> [From _Omar E. Pol_, Nov 04 2009]
%H O. E. Pol, <a href="http://www.polprimos.com/imagenespub/polca001.jpg">Illustration of initial terms of A139250, A160120, A147562 (overlapping figures)</a> [From _Omar E. Pol_, Nov 04 2009]
%H O. E. Pol, <a href="http://www.polprimos.com/imagenespub/polca033.jpg">Illustration of initial terms (overlapping circles)</a> [From _Omar E. Pol_, Jan 04 2010]
%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/toothlist.html">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F For n>0, a(n) = 1 + 4*Sum_{k=1..n} 3^(wt(k-1)-1), where wt() = A000120().
%F Contribution from Omar E. Pol, Mar 13 2011 (Start):
%F a(n) = 2*A151917(n) - 1, for n >= 1.
%F a(n) = 1 + 4*A151920(n-2), for n >= 2.
%F (End)
%e If we label the generations of cells turned ON by consecutive numbers we get a rosetta cell pattern:
%e ................4
%e ...............434
%e ..............4.2.4
%e .............4321234
%e ..............4.2.4
%e ...............434
%e ................4
%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.
%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(xpt-x) = 1 and ypt=y ) or ( x=xpt and abs(ypt-y) = 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 xmin-1 to xmax+1 do
%p for y from ymin-1 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)
%Y Cf. A000120, A139250, A147582 (number turned on at n-th step), A147610.
%Y Cf. A130665, A151920, A160120, A160410, A160414. [From _Omar E. Pol_, Nov 02 2009]
%Y Cf. A151917, A160164, A187220. - Omar E. Pol, Mar 13 2011
%K nonn,nice
%O 0,3
%A _N. J. A. Sloane_, based on emails from _Franklin T. Adams-Watters_, _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 - _R. J. Mathar_, Mar 03 2010
|
