OFFSET
-1,3
COMMENTS
We work on the square grid. A cell is turned ON iff exactly one or four of its four neighbors is ON. Once a cell is ON it stays ON. At stage -1 all cells are OFF. At stage 0 a single cell is turned ON.
This sequence also arises from Rule 467 (New Kind of Science, page 173) if we count white cells, black cells in alternate generations. - N. J. A. Sloane, Feb 04 2015
REFERENCES
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.
LINKS
N. J. A. Sloane, Table of n, a(n) for n = -1..549
David Applegate, The movie version
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. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
FORMULA
Added Apr 15 2010: The sequence is the sum of A147582(n) and 4 times A169689(4n), both of which have simple explicit formulas for the n-th term. See those two entries for details.
The sequence is generated by the following recurrence (this is true, but unnecessarily complicated): Take a(0),...,a(7) as initial values.
For n >= 8, write n = 2^k + j with 0 <= j < 2^k. Then:
a(2^k)=3a(2^(k-1))+3*2^(k-1)-8 (this is for j=0),
a(3*2^(k-1))=3a(3*2^(k-2))+2^(k+1)-24 (this is for j=2^(k-1)),
and otherwise
a(2^k+j)=a(2^(k-1)+j) for 0 < j < 2^(k-1)-1,
a(2^k+j)=3a(2^(k-1)+j) for 2^(k-1) < j < 2^k.
EXAMPLE
May be written as a triangle:
0,
1,
4,12,
8,12,12,36,
28,12,12,36,28,36,36,108,
100,12,12,36,28,36,36,108,92,36,36,108,84,108,108,324,
340,12,12,36,28,36,36,108,92,36,36,108,84,108,108,324,316,36,...
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
N. J. A. Sloane, Apr 07 2010, Apr 15 2010
STATUS
approved