0,3

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 CA. - 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.

D. Singmaster, On the cellular automaton of Ulam and Warburton, unpublished manuscript, 2003.

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.

David Applegate, The movie version

Index entries for sequences related to cellular automata

O. E. Pol, Illustration of initial terms (One-step rook) [From Omar E. Pol (info(AT)polprimos.com), Nov 02 2009]

O. E. Pol, Illustration of initial terms (One-step bishop) [From Omar E. Pol (info(AT)polprimos.com), Nov 02 2009]

O. E. Pol, Illustration of initial terms (Overlapping squares) [From Omar E. Pol (info(AT)polprimos.com), Nov 02 2009]

O. E. Pol, Illustration of initial terms (Overlapping X-toothpicks) [From Omar E. Pol (info(AT)polprimos.com), Nov 04 2009]

O. E. Pol, Illustration of initial terms of A139250, A160120, A147562(Overlapping figures) [From Omar E. Pol (info(AT)polprimos.com), Nov 04 2009]

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

If we label the generations of cells turned ON by consecutive numbers we get a rosetta cell pattern (1 should be added to these numbers to match the new offset):

................3

...............323

..............3.1.3

.............3210123

..............3.1.3

...............323

................3

In the first generation, only the central "0" is ON, a(1)=1. In the next generation, we turn ON four "1", leading to a(2)=a(1)+4=5. In the third generation, four "2" are turned ON, a(3)=a(2)+4=9. In the fourth generation, each of the four wings allows three 3's to be turned ON, a(4)=a(3)+4*3=21.

# [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)) ;

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)

Cf. A000120, A139250, A147582 (number turned on at n-th step), A147610.

Cf. A130665, A151920, A160120, A160410, A160414. [From Omar E. Pol (info(AT)polprimos.com), Nov 02 2009]

Sequence in context: A092387 A160720 A147552 this_sequence A162795 A147407 A146867

Adjacent sequences: A147559 A147560 A147561 this_sequence A147563 A147564 A147565

nonn,nice

N. J. A. Sloane (njas(AT)research.att.com), based on emails from Franklin T. Adams-Watters, Richard Mathar and David Wilson, Apr 29 2009

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