A183148 Toothpick sequence on the semi-infinite square grid with toothpicks connected by their endpoints.

0, 1, 4, 13, 22, 43, 52, 73, 94, 151, 160, 181, 202, 259, 280, 337, 394, 559, 568, 589, 610, 667, 688, 745, 802, 967, 988, 1045, 1102, 1267, 1324, 1489, 1654, 2143, 2152, 2173, 2194, 2251, 2272, 2329, 2386, 2551, 2572, 2629

Offset: 0

Author

Omar E. Pol, Mar 28 2011, Apr 03 2011

Keywords

• nonn

Comments

On the semi-infinite square grid we start with no toothpicks.

At stage 1 we place a single toothpick of length 1 which has one of its endpoints on the straight line.

New generations of toothpicks are added according to these rules: each exposed endpoint of toothpicks of the old generation must be touched by the 3 endpoints of three toothpicks of the new generation. Effectively these three toothpicks look like a T-toothpick (see A160172). The straight line that delimits the square grid acts like an impenetrable "absorbing" boundary: toothpicks may touch this line with at most one of their endpoints; these endpoints are not "exposed."

The sequence gives the number of toothpicks in the toothpick structure after n-th stage. The first differences (A183149) give the number of toothpicks added at n-th stage.

Examples

			At stage 1 place an orthogonal toothpick with one of its endpoints on the infinite straight line, so a(1) = 1. There is only one exposed endpoint.
At stage 2 place 3 toothpicks such that the structure looks like a cross, so a(2) = 1+3 = 4. There are 3 exposed endpoints.
At stage 3 place 9 toothpicks, so a(3) = 4+9 = 13. There are 3 exposed endpoints.
At stage 4 place 9 toothpicks, so a(4) = 13+9 = 22. There are 7 exposed endpoints.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..1000
• 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, pp. 31-32.
• N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Crossrefs

Cf. A139250, A147562, A151920, A183004, A183060, A183126, A183149.

Programs

Mathematica

s[n_] := 1 + 4 Sum[3^(DigitCount[k, 2, 1] - 1), {k, n - 1}]; {0}~Join~Array[3 (# + (s[#] - 1)/2) + 1 &, 43, 0] (* Michael De Vlieger, Nov 02 2022 *)

Formula

a(n) = 3*A183060(n-1) + 1.