|
| |
|
|
A147562
|
|
Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).
|
|
38
| |
|
|
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; 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
|
|
|
REFERENCES
| 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.
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
O. E. Pol, Illustration of initial terms (one-step rook - the current sequence) [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]
O. E. Pol, Illustration of initial terms (overlapping circles) [From Omar E. Pol (info(AT)polprimos.com), Jan 04 2010]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata
|
|
|
FORMULA
| For n>0, a(n) = 1 + 4*Sum_{k=1..n} 3^(wt(k-1)-1), where wt() = A000120().
Contribution 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)
|
|
|
EXAMPLE
| If we label the generations of cells turned ON by consecutive numbers we get a rosetta cell pattern:
................4
...............434
..............4.2.4
.............4321234
..............4.2.4
...............434
................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.
|
|
|
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)
|
|
|
CROSSREFS
| 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]
Cf. A151917, A160164, A187220. - Omar E. Pol, Mar 13 2011
Sequence in context: A175364 A160720 A147552 * A162795 A169707 A147407
Adjacent sequences: A147559 A147560 A147561 * A147563 A147564 A147565
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| 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
|
|
|
EXTENSIONS
| Offset and initial terms changed by N. J. A. Sloane, Jun 07 2009
Numbers in the comment adapted to the offset - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 03 2010
|
| |
|
|
