login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A147562 Number of "ON" cells at n-th stage in the "Ulam-Warburton" two-dimensional cellular automaton. 81

%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 the "Ulam-Warburton" two-dimensional 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 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

%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 n-th stage of growth of two-dimensional cellular automaton defined by Wolfram's "Rule 558" or "Rule 686" based on the 5-celled 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. 2-7.

%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="/A139250/a139250.anim.html">The movie version</a>

%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 Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polca003.jpg">Illustration of initial terms (Fig. 1: one-step rook - the current sequence)</a>, <a href="http://www.polprimos.com/imagenespub/polca005.jpg">(Fig. 2: one-step 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 X-toothpicks)</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 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 For n>0, a(n) = 1 + 4*Sum_{k=1..n} 3^(wt(k-1)-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(n-2), 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(2n-2), n >= 1. - _Omar E. Pol_, Mar 06 2015

%F It appears that a(n) = (A130665(2n-1) - 1)/3, n >= 1. - _Omar E. Pol_, Mar 07 2015

%F a(n) = 1 + 4*(A130665(n-1) - 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(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 *)

%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 n-th step), A147610, A130665, A151920, A160120, A160410, A160414, A151917, A160164, A162795, A169707, A187220, A246331.

%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 by _R. J. Mathar_, Mar 03 2010

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 09:28 EST 2018. Contains 299508 sequences. (Running on oeis4.)