cp's OEIS Frontend

A160410 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).

%I A160410 #62 Nov 02 2022 07:45:12
%S A160410 0,4,16,28,64,76,112,148,256,268,304,340,448,484,592,700,1024,1036,
%T A160410 1072,1108,1216,1252,1360,1468,1792,1828,1936,2044,2368,2476,2800,
%U A160410 3124,4096,4108,4144,4180,4288,4324,4432,4540,4864,4900,5008,5116,5440,5548,5872,6196
%N A160410 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).
%C A160410 On the infinite square grid, we consider cells to be the squares, and we start at round 0 with all cells in the OFF state, so a(0) = 0.
%C A160410 At round 1, we turn ON four cells, forming a square.
%C A160410 The rule for n > 1: A cell in turned ON iff exactly one of its four vertices is a corner vertex of the set of ON cells. So in each generation every exposed vertex turns on three new cells.
%C A160410 Therefore:
%C A160410 At Round 2, we turn ON twelve cells around the square.
%C A160410 At round 3, we turn ON twelve other cells. Three cells around of every corner of the square.
%C A160410 And so on.
%C A160410 For the first differences see the entry A161411.
%C A160410 Shows a fractal behavior similar to the toothpick sequence A139250.
%C A160410 A very similar sequence is A160414, which uses the same rule but with a(1) = 1, not 4.
%C A160410 When n=2^k then the polygon formed by ON cells is a square with side length 2^(k+1).
%C A160410 a(n) is also the area of the figure of A147562 after n generations if A147562 is drawn as overlapping squares. - _Omar E. Pol_, Nov 08 2009
%C A160410 From _Omar E. Pol_, Mar 28 2011: (Start)
%C A160410 Also, toothpick sequence starting with four toothpicks centered at (0,0) as a cross.
%C A160410 Rule: Each exposed endpoint of the toothpicks of the old generation must be touched by the endpoints of three toothpicks of new generation. (Note that these three toothpicks looks like a T-toothpick, see A160172.)
%C A160410 The sequence gives the number of toothpicks after n stages. A161411 gives the number of toothpicks added at the n-th stage.
%C A160410 (End)
%H A160410 Michael De Vlieger, <a href="/A160410/b160410.txt">Table of n, a(n) for n = 0..1000</a>
%H A160410 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 A160410 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 31.
%H A160410 Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polca023.jpg">Illustration of initial terms</a> (2009)
%H A160410 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 A160410 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F A160410 Equals 4*A130665. This provides an explicit formula for a(n). - _N. J. A. Sloane_, Jul 13 2009
%F A160410 a(2^k) = (2*(2^k))^2 for k>=0.
%e A160410 From _Omar E. Pol_, Sep 24 2015: (Start)
%e A160410 With the positive terms written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
%e A160410     4;
%e A160410    16;
%e A160410    28,  64;
%e A160410    76, 112, 148, 256;
%e A160410   268, 304, 340, 448, 484, 592, 700, 1024;
%e A160410   ...
%e A160410 Right border gives the elements of A000302 greater than 1.
%e A160410 This triangle T(n,k) shares with the triangle A256534 the terms of the column k, if k is a power of 2, for example, both triangles share the following terms: 4, 16, 28, 64, 76, 112, 256, 268, 304, 448, 1024, etc.
%e A160410 .
%e A160410 Illustration of initial terms, for n = 1..10:
%e A160410 .       _ _ _ _                         _ _ _ _
%e A160410 .      |  _ _  |                       |  _ _  |
%e A160410 .      | |  _|_|_ _ _ _ _ _ _ _ _ _ _ _|_|_  | |
%e A160410 .      | |_|  _ _     _ _     _ _     _ _  |_| |
%e A160410 .      |_ _| |  _|_ _|_  |   |  _|_ _|_  | |_ _|
%e A160410 .          | |_|  _ _  |_|   |_|  _ _  |_| |
%e A160410 .          |   | |  _|_|_ _ _ _|_|_  | |   |
%e A160410 .          |  _| |_|  _ _     _ _  |_| |_  |
%e A160410 .          | | |_ _| |  _|_ _|_  | |_ _| | |
%e A160410 .          | |_ _| | |_|  _ _  |_| | |_ _| |
%e A160410 .          |       |   | |   | |   |       |
%e A160410 .          |  _ _  |  _| |_ _| |_  |  _ _  |
%e A160410 .          | |  _|_| | |_ _ _ _| | |_|_  | |
%e A160410 .          | |_|  _| |_ _|   |_ _| |_  |_| |
%e A160410 .          |   | | |_ _ _ _ _ _ _ _| | |   |
%e A160410 .          |  _| |_ _| |_     _| |_ _| |_  |
%e A160410 .       _ _| | |_ _ _ _| |   | |_ _ _ _| | |_ _
%e A160410 .      |  _| |_ _|   |_ _|   |_ _|   |_ _| |_  |
%e A160410 .      | | |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _| | |
%e A160410 .      | |_ _| |                       | |_ _| |
%e A160410 .      |_ _ _ _|                       |_ _ _ _|
%e A160410 .
%e A160410 After 10 generations there are 304 ON cells, so a(10) = 304.
%e A160410 (End)
%t A160410 RasterGraphics[state_?MatrixQ,colors_Integer:2,opts___]:=
%t A160410 Graphics[Raster[Reverse[1-state/(colors -1)]],
%t A160410 AspectRatio ->(AspectRatio/.{opts}/.AspectRatio ->Automatic),
%t A160410 Frame ->True, FrameTicks ->None, GridLines ->None];
%t A160410 rule=1340761804646523638425234105559798690663900360577570370705802859623\
%t A160410 705267234688669629039040624964794287326910250673678735142700520276191850\
%t A160410 5902735959769690
%t A160410 Show[GraphicsArray[Map[RasterGraphics,CellularAutomaton[{rule, {2,
%t A160410 {{4,2,1}, {32,16,8}, {256,128,64}}}, {1,1}}, {{{1,1}, {1,1}}, 0}, 9,-10]]]];
%t A160410 ca=CellularAutomaton[{rule,{2,{{4,2,1},{32,16,8},{256,128,64}}},{1,
%t A160410 1}},{{{1,1},{1,1}},0},99,-100];
%t A160410 Table[Total[ca[[i]],2],{i,1,Length[ca]}]
%t A160410 (* _John W. Layman_, Sep 01 2009; Sep 02 2009 *)
%t A160410 a[n_] := 4*Sum[3^DigitCount[k, 2, 1], {k, 0, n-1}];
%t A160410 Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Nov 17 2017, after _N. J. A. Sloane_ *)
%o A160410 (PARI) A160410(n)=sum(i=0,n-1,3^norml2(binary(i)))<<2 \\ _M. F. Hasler_, Dec 04 2012
%Y A160410 Cf. A000079, A000302, A048883, A139250, A147562, A160118, A160412, A160414, A161411, A160717, A160720, A160727, A256530, A256534.
%K A160410 nonn,tabf
%O A160410 0,2
%A A160410 _Omar E. Pol_, May 20 2009
%E A160410 Edited by _David Applegate_ and _N. J. A. Sloane_, Jul 13 2009