A160722 Number of "ON" cells at n-th stage in a certain 2-dimensional cellular automaton based on Sierpinski triangles (see Comments for precise definition).

0, 1, 5, 9, 19, 23, 33, 43, 65, 69, 79, 89, 111, 121, 143, 165, 211, 215, 225, 235, 257, 267, 289, 311, 357, 367, 389, 411, 457, 479, 525, 571, 665, 669, 679, 689, 711, 721, 743, 765, 811, 821, 843, 865, 911, 933, 979, 1025, 1119, 1129, 1151, 1173, 1219, 1241

Offset

0,3

Comments

This cellular automata is formed by the concatenation of three Sierpinski triangles, starting from a central vertex. Adjacent polygons are fused. The ON cells are triangles, but we only count after fusion. The sequence gives the number of polygons at the n-th round.

If instead we start from four Sierpinski triangles we get A160720.

Links

Michael De Vlieger, 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.]

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 30.

Omar E. Pol, Illustration if initial terms

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Formula

a(n) = 3*A006046(n) - 2*n. - Max Alekseyev, Jan 21 2010

Example

We start at round 0 with no polygons, a(0) = 0.
At round 1 we turn ON the first triangle in each of the three Sierpinski triangles. After fusion we have a concave pentagon, so a(1) = 1.
At round 2 we turn ON two triangles in each the three Sierpinski triangles. After fusions we have the concave pentagon and four triangles. So a(2) = 1 + 4 = 5.

Mathematica

a[0] = 0; a[1] = 1; a[n_] := a[n] = 2 a[Floor[#]] + a[Ceiling[#]] &[n/2]; Array[3 a[#] - 2 # &, 54, 0] (* Michael De Vlieger, Nov 01 2022 *)

Crossrefs

A160723 gives the first differences.

Cf. A139250, A160720.

Sequence in context: A226663 A023521 A113805 * A255652 A061202 A235799

Adjacent sequences: A160719 A160720 A160721 * A160723 A160724 A160725

Keyword

nonn

Author

Omar E. Pol, May 25 2009, Jan 03 2010

Extensions

Extended by Max Alekseyev, Jan 21 2010

Status

approved