OFFSET
0,3
COMMENTS
On the infinite square grid we start with no toothpicks.
At stage 1 we place a single toothpick of length 1.
Rule: each exposed endpoint of the toothpicks of the old generation must be touched by the endpoints of three toothpicks of new generation.
The sequence gives the number of toothpicks after n stages. A183127 gives the number of toothpicks added at the 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, p. 31.
John W. Layman, Graphs of the toothpick configuration for generations 1-15
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
FORMULA
From Nathaniel Johnston, Apr 06 2011: (Start)
a(n) = 7 + 4*(n-2 + Sum_{k=1..n-2}3^A000120(k)), n >= 2.
a(n) = 7 + 4*(n-2 + 3*A151920(n-3)), n >= 3.
a(1 + 2^n) = 2^(n+2)+4^(n+1)-1, n >= 0.
(End)
MATHEMATICA
a[n_] := 7 + 4 (n - 2 + Sum[3^DigitCount[k, 2, 1], {k, n - 2}]); a[0] = 0; a[1] = 1; Array[a, 41, 0] (* Michael De Vlieger, Nov 02 2022 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Omar E. Pol, Mar 28 2011
EXTENSIONS
Terms a(0)-a(10) confirmed and terms a(11)-a(35) added by John W. Layman, Mar 30 2011
a(36)-a(40) from Nathaniel Johnston, Apr 06 2011
STATUS
approved