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. 80
0, 1, 5, 9, 21, 25, 37, 49, 85, 89, 101, 113, 149, 161, 197, 233, 341, 345, 357, 369, 405, 417, 453, 489, 597, 609, 645, 681, 789, 825, 933, 1041, 1365, 1369, 1381, 1393, 1429, 1441, 1477, 1513, 1621, 1633, 1669, 1705, 1813, 1849, 1957, 2065, 2389, 2401, 2437, 2473 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Studied by Holladay and Ulam circa 1960. See Fig. 1 and Example 1 of the Ulam reference. - N. J. A. Sloane, Aug 02 2009.

Singmaster calls this the Ulam-Warburton cellular automaton. - N. J. A. Sloane, Aug 05 2009

On the infinite square grid, start with all cells OFF.

Turn a single cell to the ON state.

At each subsequent step, each cell with exactly one neighbor ON is turned ON, and everything that is already ON remains ON.

Here "neighbor" refers to the four adjacent cells in the X and Y directions.

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.

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

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

It appears that the positive terms are also the odd terms (a bisection) of A151920. - Omar E. Pol, Mar 06 2015

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

REFERENCES

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

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.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191

David Applegate, The movie version

Steven Finch, Toothpicks and live cells

Omar E. Pol, Illustration of initial terms (Fig. 1: one-step rook - the current sequence), (Fig. 2: one-step bishop), (Fig. 3: overlapping squares), (Fig. 4: overlapping X-toothpicks), (2009), (Fig. 5: overlapping circles), (2010)

Omar E. Pol, Illustration of initial terms of A139250, A160120, A147562 (overlapping figures), (2009)

D. Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]

N. J. A. Sloane, Illustration of terms 0 through 9

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015

Eric Weisstein's World of Mathematics, Elementary Cellular Automaton

S. Wolfram, A New Kind of Science

Index entries for sequences related to cellular automata

Index to 2D 5-Neighbor Cellular Automata

Index to Elementary Cellular Automata

FORMULA

For n>0, a(n) = 1 + 4*Sum_{k=1..n} 3^(wt(k-1)-1), where wt() = A000120().

From Omar E. Pol, Mar 13 2011: (Start)

a(n) = 2*A151917(n) - 1, for n >= 1.

a(n) = 1 + 4*A151920(n-2), for n >= 2.

(End)

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

It appears that a(n) = A151920(2n-2), n >= 1. - Omar E. Pol, Mar 06 2015

It appears that a(n) = (A130665(2n-1) - 1)/3, n >= 1. - Omar E. Pol, Mar 07 2015

a(n) = 1 + 4*(A130665(n-1) - 1)/3, n >= 1. Omar E. Pol, Mar 07 2015

EXAMPLE

If we label the generations of cells turned ON by consecutive numbers we get a rosetta cell pattern:

. . . . . . . . . . . . . . . . .

. . . . . . . . 4 . . . . . . . .

. . . . . . . 4 3 4 . . . . . . .

. . . . . . 4 . 2 . 4 . . . . . .

. . . . . 4 3 2 1 2 3 4 . . . . .

. . . . . . 4 . 2 . 4 . . . . . .

. . . . . . . 4 3 4 . . . . . . .

. . . . . . . . 4 . . . . . . . .

. . . . . . . . . . . . . . . . .

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.

From Omar E. Pol, Feb 18 2015: (Start)

Also, written as an irregular triangle T(j,k), j>=0, k>=1, in which the row lengths are the terms of A011782:

1;

5;

9,   21;

25,  37, 49, 85;

89, 101,113,149,161,197,233,341;

345,357,369,405,417,453,489,597,609,645,681,789,825,933,1041,1365;

...

The right border gives the positive terms of A002450.

(End)

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

MAPLE

Since this is the partial sum sequence of A147582, it is most easily obtained using the Maple code given in A147582.

# [x, y] coordinates of cells on

Lse := [[0, 0]] ;

# enclosing rectangle of the cells on (that is, minima and maxima in Lse)

xmin := 0 ;

xmax := 0 ;

ymin := 0 ;

ymax := 0 ;

# count neighbors of x, y which are on; return 0 if [x, y] is in L

cntnei := proc(x, y, L)

local a, p, xpt, ypt;

a := 0 ;

if not [x, y] in L then

for p in Lse do

xpt := op(1, p) ;

ypt := op(2, p) ;

if ( abs(xpt-x) = 1 and ypt=y ) or ( x=xpt and abs(ypt-y) = 1) then

a := a+1 ;

fi;

od:

fi:

RETURN(a) ;

end:

# loop over generations/steps

for stp from 1 to 10 do

Lnew := [] ;

for x from xmin-1 to xmax+1 do

for y from ymin-1 to ymax+1 do

if cntnei(x, y, Lse) = 1 then

Lnew := [op(Lnew), [x, y]] ;

fi;

od:

od:

for p in Lnew do

xpt := op(1, p) ;

ypt := op(2, p) ;

xmin := min(xmin, xpt) ;

xmax := max(xmax, xpt) ;

ymin := min(ymin, ypt) ;

ymax := max(ymax, ypt) ;

od:

Lse := [op(Lse), op(Lnew)] ;

print(nops(Lse)) ;

MATHEMATICA

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 *)

ArrayPlot /@ CellularAutomaton[{686, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 16]

CROSSREFS

Cf. A000120, A139250, A147582 (number turned ON at n-th step), A147610, A130665, A151920, A160120, A160410, A160414, A151917, A160164, A162795, A169707, A187220, A246331.

Sequence in context: A211428 A160720 A147552 * A162795 A255366 A269522

Adjacent sequences:  A147559 A147560 A147561 * A147563 A147564 A147565

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane, based on emails from Franklin T. Adams-Watters, R. J. Mathar and David W. Wilson, Apr 29 2009

EXTENSIONS

Offset and initial terms changed by N. J. A. Sloane, Jun 07 2009

Numbers in the comment adapted to the offset by R. J. Mathar, Mar 03 2010

STATUS

approved

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 June 25 00:41 EDT 2017. Contains 288708 sequences.