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,3

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.

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

Formula

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

Example

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.

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 *)

Crossrefs

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

Sequence in context: A017209 A052218 A341005 * A202089 A339804 A256390

Adjacent sequences: A183145 A183146 A183147 * A183149 A183150 A183151

Keyword

nonn

Author

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

Status

approved