

A147562


Number of "ON" cells at nth stage in the "UlamWarburton" twodimensional cellular automaton.


91



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 UlamWarburton 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 "onestep rook" adjacencies is isomorphic to Z^2 with "onestep bishop" adjacencies.
Also toothpick sequence starting with a central Xtoothpick followed by Ttoothpicks (see A160170 and A160172). The sequence gives the number of polytoothpicks in the structure after nth 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 nth stage of growth of twodimensional cellular automaton defined by Wolfram's "Rule 558" or "Rule 686" based on the 5celled von Neumann neighborhood.  Robert Price, May 10 2016
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.
a(n) is also the total number of "flowers with six petals" after 4*n stages in the toothpick structure of A323650.
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 "onestep bishop" of this sequence (see the illustration of initial terms, figure 2). (End)


REFERENCES

S. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215224 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



FORMULA

a(n) = 1 + 4*Sum_{k=1..n1} 3^(wt(k)1) for n>1, where wt() = A000120(). [Corrected by Paolo Xausa, Aug 12 2022]
a(n) = 2*A151917(n)  1, for n >= 1.
a(n) = 1 + 4*A151920(n2), for n >= 2.
(End)


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.
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(xptx) = 1 and ypt=y ) or ( x=xpt and abs(ypty) = 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 xmin1 to xmax+1 do
for y from ymin1 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

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 *)
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 *)
A147562list[nmax_]:=Accumulate[Join[{0, 1}, 4*3^(DigitCount[Range[nmax1], 2, 1]1)]]; A147562list[100] (* Paolo Xausa, May 21 2023 *)


PROG

(PARI) a(n) = if (n, 1 + 4*sum(k=1, n1, 3^(hammingweight(k)1)), 0); \\ Michel Marcus, Jul 05 2022


CROSSREFS

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


KEYWORD

nonn,nice


AUTHOR



EXTENSIONS

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


STATUS

approved



