A183148 - OEIS

%I #20 Nov 02 2022 11:53:58

%S 0,1,4,13,22,43,52,73,94,151,160,181,202,259,280,337,394,559,568,589,

%T 610,667,688,745,802,967,988,1045,1102,1267,1324,1489,1654,2143,2152,

%U 2173,2194,2251,2272,2329,2386,2551,2572,2629

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

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

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

%C 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."

%C 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.

%H Michael De Vlieger, <a href="/A183148/b183148.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, pp. 31-32.

%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>

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

%e 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.

%e 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.

%e At stage 3 place 9 toothpicks, so a(3) = 4+9 = 13. There are 3 exposed endpoints.

%e At stage 4 place 9 toothpicks, so a(4) = 13+9 = 22. There are 7 exposed endpoints.

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

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

%K nonn

%O 0,3

%A _Omar E. Pol_, Mar 28 2011, Apr 03 2011