login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A160410 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition). 22

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:23 EDT 2024. Contains 371264 sequences. (Running on oeis4.)