# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a147562
Showing 1-1 of 1

%I A147562 #184 Nov 06 2024 14:19:23
%S A147562 0,1,5,9,21,25,37,49,85,89,101,113,149,161,197,233,341,345,357,369,
%T A147562 405,417,453,489,597,609,645,681,789,825,933,1041,1365,1369,1381,1393,
%U A147562 1429,1441,1477,1513,1621,1633,1669,1705,1813,1849,1957,2065,2389,2401,2437,2473
%N A147562 Number of "ON" cells at n-th stage in the "Ulam-Warburton" two-dimensional cellular automaton.
%C A147562 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 A147562 Singmaster calls this the Ulam-Warburton cellular automaton. - _N. J. A. Sloane_, Aug 05 2009
%C A147562 On the infinite square grid, start with all cells OFF.
%C A147562 Turn a single cell to the ON state.
%C A147562 At each subsequent step, each cell with exactly one neighbor ON is turned ON, and everything that is already ON remains ON.
%C A147562 Here "neighbor" refers to the four adjacent cells in the X and Y directions.
%C A147562 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 A147562 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 A147562 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 A147562 It appears that the positive terms are also the odd terms (a bisection) of A151920. - _Omar E. Pol_, Mar 06 2015
%C A147562 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
%C A147562 From _Omar E. Pol_, Mar 05 2019: (Start)
%C A147562 a(n) is also the total number of "hidden crosses" after 4*n stages in the toothpick structure of A139250, including the central cross, beginning to count the crosses when their nuclei are totally formed with 4 quadrilaterals.
%C A147562 a(n) is also the total number of "flowers with six petals" after 4*n stages in the toothpick structure of A323650.
%C A147562 Note that the location of the "nuclei of the hidden crosses" and the "flowers with six petals" in both toothpick structures is essentially the same as the location of the "ON" cells in the version "one-step bishop" of this sequence (see the illustration of initial terms, figure 2). (End)
%C A147562 This sequence has almost exactly the same graph as A187220, A162795, A169707 and A160164 which is twice A139250. - _Omar E. Pol_, Jun 18 2022
%D A147562 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 A147562 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.
%H A147562 N. J. A. Sloane, <a href="/A147562/b147562.txt">Table of n, a(n) for n = 0..10000</a>
%H A147562 David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a>
%H A147562 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 A147562 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 A147562 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 31.
%H A147562 Bradley Klee, <a href="/A147562/a147562_1.png">Log-periodic coloring of the first quadrant, over the chair tiling</a>.
%H A147562 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 A147562 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 A147562 David Singmaster, <a href="https://m500.org.uk/wp-content/uploads/2023/11/M195WEB.pdf#page=4">On the cellular automaton of Ulam and Warburton</a>, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.  Also <a href="/A079314/a079314.pdf">scanned annotated cached copy</a>, included with permission.
%H A147562 N. J. A. Sloane, <a href="/A147562/a147562.png">Illustration of terms 0 through 9</a>
%H A147562 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 A147562 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 A147562 N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=9ogbsh8KuEM">Exciting Number Sequences</a> (video of talk), Mar 05 2021
%H A147562 N. J. A. Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=_UtCli1SgjI">Terrific Toothpick Patterns</a>, Numberphile video (2018).
%H A147562 Mike Warburton, <a href="https://arxiv.org/abs/1901.10565">Ulam-Warburton Automaton - Counting Cells with Quadratics</a>, arXiv:1901.10565 [math.CO], 2019.
%H A147562 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>
%H A147562 S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>
%H A147562 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%H A147562 <a href="/wiki/Index_to_2D_5-Neighbor_Cellular_Automata">Index to 2D 5-Neighbor Cellular Automata</a>
%H A147562 <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>
%F A147562 a(n) = 1 + 4*Sum_{k=1..n-1} 3^(wt(k)-1) for n>1, where wt() = A000120(). [Corrected by _Paolo Xausa_, Aug 12 2022]
%F A147562 For asymptotics see the discussion in the comments in A006046. - _N. J. A. Sloane_, Mar 11 2021
%F A147562 From _Omar E. Pol_, Mar 13 2011: (Start)
%F A147562 a(n) = 2*A151917(n) - 1, for n >= 1.
%F A147562 a(n) = 1 + 4*A151920(n-2), for n >= 2.
%F A147562 (End)
%F A147562 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 A147562 It appears that a(n) = A151920(2n-2), n >= 1. - _Omar E. Pol_, Mar 06 2015
%F A147562 It appears that a(n) = (A130665(2n-1) - 1)/3, n >= 1. - _Omar E. Pol_, Mar 07 2015
%F A147562 a(n) = 1 + 4*(A130665(n-1) - 1)/3, n >= 1. _Omar E. Pol_, Mar 07 2015
%F A147562 a(n) = A323650(2n)/3. - _Omar E. Pol_, Mar 04 2019
%e A147562 If we label the generations of cells turned ON by consecutive numbers we get a rosetta cell pattern:
%e A147562 . . . . . . . . . . . . . . . . .
%e A147562 . . . . . . . . 4 . . . . . . . .
%e A147562 . . . . . . . 4 3 4 . . . . . . .
%e A147562 . . . . . . 4 . 2 . 4 . . . . . .
%e A147562 . . . . . 4 3 2 1 2 3 4 . . . . .
%e A147562 . . . . . . 4 . 2 . 4 . . . . . .
%e A147562 . . . . . . . 4 3 4 . . . . . . .
%e A147562 . . . . . . . . 4 . . . . . . . .
%e A147562 . . . . . . . . . . . . . . . . .
%e A147562 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 A147562 From _Omar E. Pol_, Feb 18 2015: (Start)
%e A147562 Also, written as an irregular triangle T(j,k), j>=0, k>=1, in which the row lengths are the terms of A011782:
%e A147562 1;
%e A147562 5;
%e A147562 9,   21;
%e A147562 25,  37, 49, 85;
%e A147562 89, 101,113,149,161,197,233,341;
%e A147562 345,357,369,405,417,453,489,597,609,645,681,789,825,933,1041,1365;
%e A147562 ...
%e A147562 The right border gives the positive terms of A002450.
%e A147562 (End)
%e A147562 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 A147562 Since this is the partial sum sequence of A147582, it is most easily obtained using the Maple code given in A147582.
%p A147562 # [x,y] coordinates of cells on
%p A147562 Lse := [[0,0]] ;
%p A147562 # enclosing rectangle of the cells on (that is, minima and maxima in Lse)
%p A147562 xmin := 0 ;
%p A147562 xmax := 0 ;
%p A147562 ymin := 0 ;
%p A147562 ymax := 0 ;
%p A147562 # count neighbors of x,y which are on; return 0 if [x,y] is in L
%p A147562 cntnei := proc(x,y,L)
%p A147562 local a,p,xpt,ypt;
%p A147562 a := 0 ;
%p A147562 if not [x,y] in L then
%p A147562 for p in Lse do
%p A147562 xpt := op(1,p) ;
%p A147562 ypt := op(2,p) ;
%p A147562 if ( abs(xpt-x) = 1 and ypt=y ) or ( x=xpt and abs(ypt-y) = 1) then
%p A147562 a := a+1 ;
%p A147562 fi;
%p A147562 od:
%p A147562 fi:
%p A147562 RETURN(a) ;
%p A147562 end:
%p A147562 # loop over generations/steps
%p A147562 for stp from 1 to 10 do
%p A147562 Lnew := [] ;
%p A147562 for x from xmin-1 to xmax+1 do
%p A147562 for y from ymin-1 to ymax+1 do
%p A147562 if cntnei(x,y,Lse) = 1 then
%p A147562 Lnew := [op(Lnew),[x,y]] ;
%p A147562 fi;
%p A147562 od:
%p A147562 od:
%p A147562 for p in Lnew do
%p A147562 xpt := op(1,p) ;
%p A147562 ypt := op(2,p) ;
%p A147562 xmin := min(xmin,xpt) ;
%p A147562 xmax := max(xmax,xpt) ;
%p A147562 ymin := min(ymin,ypt) ;
%p A147562 ymax := max(ymax,ypt) ;
%p A147562 od:
%p A147562 Lse := [op(Lse),op(Lnew)] ;
%p A147562 print(nops(Lse)) ;
%t A147562 Join[{0},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; modified by _Paolo Xausa_, Aug 12 2022 to include the a(0) term *)
%t A147562 ArrayPlot /@ CellularAutomaton[{686, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 16] (* _N. J. A. Sloane_, Nov 08 2014 *)
%t A147562 A147562list[nmax_]:=Accumulate[Join[{0,1},4*3^(DigitCount[Range[nmax-1],2,1]-1)]];A147562list[100] (* _Paolo Xausa_, May 21 2023 *)
%o A147562 (PARI) a(n) = if (n, 1 + 4*sum(k=1, n-1, 3^(hammingweight(k)-1)), 0); \\ _Michel Marcus_, Jul 05 2022
%Y A147562 Cf. A000120, A139250, A147582 (number turned ON at n-th step), A147610, A130665, A151920, A151917, A160120, A160164, A160410, A160414, A162795, A169707, A187220, A246331, A323650.
%Y A147562 See also A006046, A335794, A335795.
%K A147562 nonn,nice,changed
%O A147562 0,3
%A A147562 _N. J. A. Sloane_, based on emails from _Franklin T. Adams-Watters_, _R. J. Mathar_ and _David W. Wilson_, Apr 29 2009
%E A147562 Offset and initial terms changed by _N. J. A. Sloane_, Jun 07 2009
%E A147562 Numbers in the comment adapted to the offset by _R. J. Mathar_, Mar 03 2010

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE