|
%I #32 Feb 24 2021 02:48:18
%S 0,1,9,13,41,49,101,113,189,205,305,325,449,473,621,649,821,853,1049,
%T 1085,1305,1345,1589,1633,1901,1949,2241,2293,2609,2665,3005,3065,
%U 3429,3493,3881,3949,4361,4433,4869,4945,5405,5485,5969,6053,6561,6649,7181,7273
%N Number of "ON" cells after n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).
%C Define "peninsula cell" to be the "ON" cell connected to the structure by exactly one of its vertices.
%C Define "bridge cell" to be the "ON" cell connected to two cells of the structure by exactly consecutive two of its vertices.
%C On the infinite square grid, we start at stage 0 with all cells in OFF state. At stage 1, we turn ON a single cell, in the central position.
%C In order to construct this sequence we use the following rules:
%C - If n is even, we turn "ON" the cells around the cells turned "ON" at the generation n-1.
%C - If n is odd, we turn "ON" the possible bridge cells and the possible peninsula cells.
%C - Everything that is already ON remains ON.
%C A160411, the first differences, gives the number of cells turned "ON" at n-th stage.
%H Alois P. Heinz, <a href="/A160117/b160117.txt">Table of n, a(n) for n = 0..1000</a>
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, 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.]
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F a(2n) = 5 + 2n(7n-5) for n>=1, a(2n+1) = 5 + 2n(7n-3) for n>=1. - _Nathaniel Johnston_, Nov 06 2010
%F G.f.: x*(x^2+1)*(4*x^3+x^2+8*x+1)/((x+1)^2*(1-x)^3). - _Alois P. Heinz_, Sep 16 2011
%e If we label the generations of cells turned ON by consecutive numbers we get the cell pattern shown below:
%e 9...9...9...9...9
%e .888.888.888.888.
%e .878.878.878.878.
%e .886668666866688.
%e 9..656.656.656..9
%e .886644464446688.
%e .878.434.434.878.
%e .886644222446688.
%e 9..656.212.656..9
%e .886644222446688.
%e .878.434.434.878.
%e .886644464446688.
%e 9..656.656.656..9
%e .886668666866688.
%e .878.878.878.878.
%e .888.888.888.888.
%e 9...9...9...9...9
%e At the first generation, only the central "1" is ON, so a(1) = 1. At the second generation, we turn ON eight cells around the central cell, leading to a(2) = a(1)+8 = 9. At the third generation, we turn ON four peninsula cells, so a(3) = a(2)+4 = 13. At the fourth generation, we turn ON the cells around the cells turned ON at the third generation, so a(4) = a(3)+28 = 41. At the 5th generation, we turn ON four peninsula cells and four bridge cells, so a(5) = a(4)+8 = 49.
%p a:= proc(n) local r;
%p r:= irem(n, 2);
%p `if`(n<2, n, 5+(n-r)*((7*n-3*r)/2-5))
%p end:
%p seq(a(n), n=0..80); # _Alois P. Heinz_, Sep 16 2011
%t a[0] = 0; a[1] = 1; a[n_] := If[EvenQ[n], (7n^2 - 10n + 10)/2, (7n^2 - 20n + 23)/2]; Table[a[n], {n, 0, 80}] (* _Jean-François Alcover_, Jul 16 2015, after _Nathaniel Johnston_ *)
%Y Cf. A139250, A139251, A147562, A160118, A160119, A160379.
%K nonn
%O 0,3
%A _Omar E. Pol_, May 05 2009, May 15 2009
%E a(10) - a(27) from _Nathaniel Johnston_, Nov 06 2010
%E a(28) - a(47) from _Alois P. Heinz_, Sep 16 2011
|
