%I #62 Nov 02 2022 07:45:12
%S 0,4,16,28,64,76,112,148,256,268,304,340,448,484,592,700,1024,1036,
%T 1072,1108,1216,1252,1360,1468,1792,1828,1936,2044,2368,2476,2800,
%U 3124,4096,4108,4144,4180,4288,4324,4432,4540,4864,4900,5008,5116,5440,5548,5872,6196
%N Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).
%C 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 At round 1, we turn ON four cells, forming a square.
%C 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 Therefore:
%C At Round 2, we turn ON twelve cells around the square.
%C At round 3, we turn ON twelve other cells. Three cells around of every corner of the square.
%C And so on.
%C For the first differences see the entry A161411.
%C Shows a fractal behavior similar to the toothpick sequence A139250.
%C A very similar sequence is A160414, which uses the same rule but with a(1) = 1, not 4.
%C When n=2^k then the polygon formed by ON cells is a square with side length 2^(k+1).
%C 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 From _Omar E. Pol_, Mar 28 2011: (Start)
%C Also, toothpick sequence starting with four toothpicks centered at (0,0) as a cross.
%C 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 The sequence gives the number of toothpicks after n stages. A161411 gives the number of toothpicks added at the n-th stage.
%C (End)
%H Michael De Vlieger, <a href="/A160410/b160410.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 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 Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polca023.jpg">Illustration of initial terms</a> (2009)
%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 Equals 4*A130665. This provides an explicit formula for a(n). - _N. J. A. Sloane_, Jul 13 2009
%F a(2^k) = (2*(2^k))^2 for k>=0.
%e From _Omar E. Pol_, Sep 24 2015: (Start)
%e With the positive terms written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
%e 4;
%e 16;
%e 28, 64;
%e 76, 112, 148, 256;
%e 268, 304, 340, 448, 484, 592, 700, 1024;
%e ...
%e Right border gives the elements of A000302 greater than 1.
%e 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 .
%e Illustration of initial terms, for n = 1..10:
%e . _ _ _ _ _ _ _ _
%e . | _ _ | | _ _ |
%e . | | _|_|_ _ _ _ _ _ _ _ _ _ _ _|_|_ | |
%e . | |_| _ _ _ _ _ _ _ _ |_| |
%e . |_ _| | _|_ _|_ | | _|_ _|_ | |_ _|
%e . | |_| _ _ |_| |_| _ _ |_| |
%e . | | | _|_|_ _ _ _|_|_ | | |
%e . | _| |_| _ _ _ _ |_| |_ |
%e . | | |_ _| | _|_ _|_ | |_ _| | |
%e . | |_ _| | |_| _ _ |_| | |_ _| |
%e . | | | | | | | |
%e . | _ _ | _| |_ _| |_ | _ _ |
%e . | | _|_| | |_ _ _ _| | |_|_ | |
%e . | |_| _| |_ _| |_ _| |_ |_| |
%e . | | | |_ _ _ _ _ _ _ _| | | |
%e . | _| |_ _| |_ _| |_ _| |_ |
%e . _ _| | |_ _ _ _| | | |_ _ _ _| | |_ _
%e . | _| |_ _| |_ _| |_ _| |_ _| |_ |
%e . | | |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _| | |
%e . | |_ _| | | |_ _| |
%e . |_ _ _ _| |_ _ _ _|
%e .
%e After 10 generations there are 304 ON cells, so a(10) = 304.
%e (End)
%t RasterGraphics[state_?MatrixQ,colors_Integer:2,opts___]:=
%t Graphics[Raster[Reverse[1-state/(colors -1)]],
%t AspectRatio ->(AspectRatio/.{opts}/.AspectRatio ->Automatic),
%t Frame ->True, FrameTicks ->None, GridLines ->None];
%t rule=1340761804646523638425234105559798690663900360577570370705802859623\
%t 705267234688669629039040624964794287326910250673678735142700520276191850\
%t 5902735959769690
%t Show[GraphicsArray[Map[RasterGraphics,CellularAutomaton[{rule, {2,
%t {{4,2,1}, {32,16,8}, {256,128,64}}}, {1,1}}, {{{1,1}, {1,1}}, 0}, 9,-10]]]];
%t ca=CellularAutomaton[{rule,{2,{{4,2,1},{32,16,8},{256,128,64}}},{1,
%t 1}},{{{1,1},{1,1}},0},99,-100];
%t Table[Total[ca[[i]],2],{i,1,Length[ca]}]
%t (* _John W. Layman_, Sep 01 2009; Sep 02 2009 *)
%t a[n_] := 4*Sum[3^DigitCount[k, 2, 1], {k, 0, n-1}];
%t Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Nov 17 2017, after _N. J. A. Sloane_ *)
%o (PARI) A160410(n)=sum(i=0,n-1,3^norml2(binary(i)))<<2 \\ _M. F. Hasler_, Dec 04 2012
%Y Cf. A000079, A000302, A048883, A139250, A147562, A160118, A160412, A160414, A161411, A160717, A160720, A160727, A256530, A256534.
%K nonn,tabf
%O 0,2
%A _Omar E. Pol_, May 20 2009
%E Edited by _David Applegate_ and _N. J. A. Sloane_, Jul 13 2009
|