OFFSET
0,2
COMMENTS
On an infinite binary cell grid, the next generation is evaluated whereby each cell is set if it has exactly one neighbor in the Moore neighborhood, if this is not satisfied, the cell dies.
Starting with an initial configuration of a single cell, the cell population totals that follow each evaluation are the terms of this sequence.
As such each odd generation has a population 8 times that of the preceding generation, where each remaining isolated cell spawns each of its eight neighbors while itself dying, unable to satisfy the lone survival rule.
Observing the even generations, A pattern is followed where cell population rises following local increments of 4^n, before hitting a global maximum and 'collapsing' down to 4 cells, the 4 absolute corners of population evaluated so far. The process repeats from each corner until each corner expansion meets, triggering the next collapse.
The collapse behavior can be explained by 3 observations.
A single uninterrupted cell will expand by 1 cell each generation, in each direction.
When a critical density is reached, only the 4 corners satisfy the birth rule.
As the population expands, it approaches that density, achieving it as each quadrant meets at the center origin lines.
With an initial configuration of a single cell at (0,0),
A collapse at generation k therefore will create corner cells a distance k cells from origin.
Likewise, it'll take k generations to expand back to the origin and trigger the next collapse.
or, the n-th collapse at generation (k) will precede the (n+1)th collapse at generation 2k.
Given The first collapse occurs at generation 2.
so then the 4th collapse will occur at 2(2(2(2))) = 2^4 = 16.
Cell count collapses to 4 on every 2^n generation where n>0.
From this, we can take that the n-th collapse occurs at 2^(n).
This holds since 2*(2^(n-1)) = 2^n.
Given the above growth of 2 cells over each axis for each generation, Bounding Area of population at n-th generation can be given by
area(n) = (2n + ICw) * (2n + ICh) where ICw and ICh is the width and height of the initial configuration
LINKS
Jonathan Amery-Behr, Table of n, a(n) for n = 0..9999
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.] (2010)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
FORMULA
if (n mod 2 == 0), a(n+1) = 8*a(n);
if (n mod 2 == 1), 4^( Sum of all '1's in binary expansion of n).
MATHEMATICA
a[n_] := a[n] = If[OddQ[n], 8 a[n - 1], 4^Total[IntegerDigits[n, 2]]];
a /@ Range[0, 100] (* Jean-François Alcover, Oct 23 2019 *)
PROG
(PARI) {a(n) = if(mod(n, 2), 8*(4^subst(Pol( binary(n-1)), x, 1)), 4^ subst( Pol(binary(n)), x, 1))}
CROSSREFS
KEYWORD
nonn
AUTHOR
Jonathan Amery-Behr, Feb 27 2013
STATUS
approved