betaFeedback

WorksMathematics

On the V-toothpick sequence

Abstract

We give a generating function for the V-toothpick sequence and an algorithm that computes any term in time polynomial in the number of binary digits of its index. We determine its quadratic growth and periodic fluctuations, and give convergent series for the constants in its asymptotic bounds.

Notation and conventions

We write N={0,1,2,…}\mathbb{N}=\{0,1,2,\ldots\} and Z\mathbb{Z} for the integers, and use log⁡2\log_2 for the binary logarithm and log⁡\log for the natural logarithm. An integer is dyadic if it is a power of two. For m≥1m \ge1, lb⁡(m)\operatorname{lb}(m) is the largest power of two dividing mm. For m≥0m \ge0, s2(m)s_2(m) counts the ones in its binary expansion. For nonnegative integers, x&yx \mathbin{\&} y has binary digits equal to the products of the corresponding digits of xx and yy. Thus x&y=0x \mathbin{\&} y=0 when they have no common digit equal to one.

Generating-function identities are understood as identities of formal power series. We write [zj]Q[z^j]Q for the coefficient of zjz^j in QQ, with value zero for j<0j<0. For a polynomial QQ, supp⁡(Q)\operatorname{supp}(Q) is the set of its nonzero coefficient indices, #supp⁡(Q)\#\operatorname{supp}(Q) its size, and ∥Q∥\lVert Q\rVert the sum of the absolute values of its coefficients. The indicator 1E\mathbf{1}_{\mathcal{E}} is 1 when the condition E\mathcal{E} holds and 0 otherwise. For n≥0n \ge0, we set (nj)=0\binom{n}{j}=0 unless 0≤j≤n0 \le j \le n.

Introduction

From toothpicks to the honeycomb

Omar E. Pol introduced the toothpick sequence, OEIS A139250, in 2008 [7]. Starting with one segment on the square lattice, the construction adds a perpendicular segment whose midpoint meets each exposed end. Applegate, Pol, and Sloane [2] studied this sequence in 2010, giving recurrences based on powers of two, generating functions, and asymptotic results. They also related the growth to the Ulam-Warburton cellular automaton and examined other local rules.

Pol introduced the V-toothpick variant in 2009 as A161206 [7]. Its pieces lie on the honeycomb lattice, and the counting mechanism of the square-lattice construction does not directly apply. The OEIS entry describes the growth but gives no general formula for its terms. We obtain an expression for its generating function, an algorithm for an arbitrary term, and its leading asymptotic form. The algorithm computes a term without computing all preceding terms. To our knowledge, this is the first such representation and algorithm with polynomial cost in the binary input length for this variant.

Consider the honeycomb lattice, that is, the tiling of the plane by regular hexagons with sides of length one. A V-toothpick is a piece made of two sides of the lattice that meet at a vertex at an angle of 120 degrees. This vertex is the apex of the piece and the two other endpoints are its ends.

The game starts with an empty plane. At round 1 one piece is placed. At each later round a new piece is placed at every free end of the structure. A free end is an end of a piece that touches no other piece. The new piece has its apex at the free end and covers the two other sides of the lattice that leave this vertex. All pieces of a round are placed simultaneously. When two new pieces reach the same vertex in the same round, this vertex is not a free end and nothing grows from it later. Figure 1 shows the first rounds and Figure 2 shows the structure after 32 rounds.

Figure 1. The structure after rounds 1, 2, 3, 4, and 6. The pieces of the last round are in red and the dots are the free ends.

Figure 2. The V-toothpick structure after 32 rounds. It contains a(32)=1005a(32)=1005 pieces.

Let a(n)a(n) be the number of pieces after nn rounds, with a(0)=0a(0)=0, and let t(n)=a(n)−a(n−1)t(n)=a(n)-a(n-1) be the number of pieces placed at round nn. The first values are

a(n)=0, 1, 3, 7, 13, 21, 31, 43, 57, 69, 81, 99, 123,…a(n)=0,\ 1,\ 3,\ 7,\ 13,\ 21,\ 31,\ 43,\ 57,\ 69,\ 81,\ 99,\ 123,\ldots

The increments form entry A161207 of the OEIS [7].

The question

The definition gives a(n)a(n) by playing the game through all the preceding rounds. Finite propagation places every affected vertex in a region with O(n2)O(n^2) sites. A direct simulation visits successive fronts in this region, whereas the question here is whether one can recover the count from the binary expansion of nn. Even the number of simulated rounds is exponential in the length of that input.

The irregular increments in Figure 3 suggest that the dyadic repetition is more complicated than for the original toothpick sequence. We seek a description that accounts for all vertices that appear inside each region, including those reached when growing parts of the structure meet.

Figure 3. The number t(n)t(n) of pieces placed at round nn, for n≤256n \le256. The dotted lines mark the powers of two.

Results

We use polynomials to count the vertices that appear at successive times under the local growth rule of § 3. Each appearance is called a birth. The polynomials P2,P4,P8,…P_2,P_4,P_8,\ldots are indexed by the powers of two. The polynomial PqP_q counts, round by round, the births in a finite region of the structure that we call a diamond of size qq. Its definition is given in § 3. The first two are P2=1+zP_2=1+z and P4=1+2z+2z2+z3+2z4+2z5P_4=1+2z+2z^2+z^3+2z^4+2z^5. The cone polynomial CrC_r counts births in a triangular region of size rr, also defined there. Set

G(w)=∏i≥0(1+2w2i)=∑j≥02s2(j)wj.G(w)=\prod_{i\ge0}(1+2w^{2^i})=\sum_{j\ge0}2^{s_2(j)}w^j.

Theorem 1. Let A(z)=∑n≥0a(n)znA(z)=\sum_{n\ge0}a(n)z^n. In the ring of formal power series,

A(z)=(1+z)(1+2z2)1−z(z1−z+2∑q=2,4,8,…z2q+1Pq(z)1−z4q).(1)A(z)=\frac{(1+z)(1+2z^2)}{1-z}\left(\frac{z}{1-z}+2\sum_{q=2,4,8,\ldots}\frac{z^{2q+1}P_q(z)}{1-z^{4q}}\right). \tag*{(1)}

The equivalent expression in terms of cones is

A(z)=(1+z)(1+2z2)1−z(z1−z+2∑q=2,4,8,…z2q(Cq(z)−1)G(z4q)).A(z)=\frac{(1+z)(1+2z^2)}{1-z}\left(\frac{z}{1-z}+2\sum_{q=2,4,8,\ldots}z^{2q}(C_q(z)-1)G(z^{4q})\right).

Each term of the first sum says that a diamond of size qq appears for the first time at a fixed round and then again every 4q4q rounds. Only the terms with 2q+1≤n2q+1\le n contribute to the coefficient of znz^n, so the sum is well defined.

For example, the contribution of q=2q=2 to the increment series (1−z)A(z)(1-z)A(z) begins with

2z5(1+z)2(1+2z2)=2z5+4z6+6z7+8z8+4z9.2z^5(1+z)^2(1+2z^2)=2z^5+4z^6+6z^7+8z^8+4z^9.

The rational term contributes 6 at each round n≥4n\ge4. Hence t(5)=8t(5)=8, t(6)=10t(6)=10, and t(7)=12t(7)=12, which give a(5)=21a(5)=21, a(6)=31a(6)=31, and a(7)=43a(7)=43.

The geometric construction in § 4 shows that PqP_q has at least 2q−22q-2 nonzero coefficients. Expanding a polynomial of size comparable to nn would therefore require at least as many operations. The following algorithm avoids this expansion. The class FP consists of functions computable in time polynomial in the length of the input [3].

Theorem 2. There is an algorithm that takes as input the binary expansion of an integer n≥0n\ge0 and returns a(n)a(n) and t(n)t(n). With ℓ=⌊log⁡2(n+3)⌋+1\ell=\lfloor\log_2(n+3)\rfloor+1, it performs O(ℓ8)O(\ell^8) arithmetic operations on integers of O(ℓ)O(\ell) bits. In particular the maps n↦a(n)n\mapsto a(n) and n↦t(n)n\mapsto t(n) belong to the class FP.

Here the input has length of order log⁡n\log n, so the running time is polynomial in log⁡n\log n. The same program works for every nn and needs no precomputed table. We do not claim that the exponent 8 is optimal. The computations in Section 6 include indices up to 1010010^{100}, with the outputs checked by two separately written implementations.

The number of births in a diamond of size qq is asymptotic to κq2\kappa q^2 for a computable constant κ=0.6879156855…\kappa= 0.6879156855\ldots. Theorem 32 shows that

a(n)=n2Ψ(n2k)+O(nlog⁡23(log⁡n)2),k=⌊log⁡2n⌋,a(n)=n^2\Psi\left(\frac{n}{2^k}\right)+O\left(n^{\log_2 3}(\log n)^2\right), \qquad k=\lfloor\log_2 n\rfloor,

for a continuous function Ψ\Psi on [1,2][1,2] determined by two functional equations. The ratio a(n)/n2a(n)/n^2 has no limit. Its lower and upper limits are 9κ/89\kappa/8 and 3κ/23\kappa/2. Theorem 25 gives a series for κ\kappa whose first NN terms have error at most 4/3N4/3^N and require cones of size at most 4N4N.

Theorem 34 also shows that the differences Xk=C2k−C2k−1X_k=C_{2^k}-C_{2^k-1} have only O(k3)O(k^3) nonzero coefficients. It computes these coefficients using cones and triangles of size O(k)O(k).

The recursive construction computes its initial data by applying the growth rule to triangles of side O(log⁡n)O(\log n). Whether a fixed finite family of numerical recurrences suffices remains open.

Geometric reduction and coefficient extraction

Earliest births follow Pascal’s triangle modulo 2. Along certain lines of constant coordinate sum, this pattern prevents further growth and separates the structure into finite diamonds. The repeated occurrence of a diamond of size qq, every 4q4q rounds, gives the denominator in (1).

Each diamond reduces to smaller diamonds and cones. A translation identity for truncated triangles then reduces the cones, except for domains of size O(log⁡n)O(\log n). The algorithm stores these identities as a graph of polynomial expressions. A coefficient or a partial sum is evaluated by following this graph. The queried indices lie in a polynomial number of residue classes modulo the dyadic sizes, which bounds the number of evaluations.

Related work

The square-lattice analysis of Applegate, Pol, and Sloane [2] provides the closest enumerative comparison. Here the relevant finite regions also occur at dyadic scales, but their evolution requires additional cone polynomials. Their reduction gives a uniform algorithm as the queried index grows.

The complexity of prediction for cellular automata depends on the rule and the input model. Neary and Woods [5] show that predicting Rule 110 can encode any decision problem solvable in polynomial time, through a transformation using logarithmic space. Such results concern families of initial configurations and a prediction task. Our input consists only of a time index, with a fixed initial seed, and our output is a global count. We make no claim about prediction from arbitrary initial data.

The representation used below is related to random access in compressed objects. Bille et al. [4] retrieve characters from a string specified by a grammar that generates that string alone, without expanding it. Our nodes instead describe signed sums of shifted, potentially overlapping polynomials. The residue lemma is needed to bound how many coefficient queries these sums generate.

The model and the birth polynomials

The lattice and the growth rule

All time indices start at 0, unless global round numbers are specified. We describe the honeycomb lattice as a bipartite graph. Its vertices are the points A(x,y)A(x,y) and B(x,y)B(x,y) with (x,y)∈Z2(x,y)\in\mathbb{Z}^2. We also write A(x,y)=(0,x,y)A(x,y)=(0,x,y) and B(x,y)=(1,x,y)B(x,y)=(1,x,y), so that a vertex is a triple (p,x,y)(p,x,y) with p∈{0,1}p \in\{0,1\}. The neighbors of A(x,y)A(x,y) are B(x,y)B(x,y), B(x−1,y)B(x-1,y), and B(x,y−1)B(x,y-1). Consequently the neighbors of B(x,y)B(x,y) are A(x,y)A(x,y), A(x+1,y)A(x+1,y), and A(x,y+1)A(x,y+1).

Definition 3. Let DD be a set of vertices and let s∈Ds \in D be a vertex called the seed. Time is discrete. Every vertex of DD other than the seed is initially intact. The seed is born at time 0. At each time t≥0t \ge0 every vertex born at time tt sends a proposal to each of its neighbors in DD. An intact vertex that receives exactly one proposal at time t+1t+1 is born at time t+1t+1. An intact vertex that receives two or three proposals at time t+1t+1 is blocked. A vertex that is born or blocked is never modified again and ignores later proposals. The birth polynomial of (D,s)(D,s) is the sum of ztz^t over the vertices born at time tt. When DD is infinite it is a formal power series.

A born vertex emits once, at the time that follows its birth. A blocked vertex never emits.

Remark 4. In a finite domain with NN vertices, a birth at time t≥1t \ge1 requires a birth at time t−1t-1. Thus the birth polynomial has degree at most N−1N-1.

Lemma 5. Run the growth of Definition 3 on the whole lattice with seed A(0,0)A(0,0), with the single change that the seed sends proposals to two of its three neighbors only. Then for every n≥1n \ge1 the number t(n)t(n) of pieces placed at round nn is the number of vertices born at time n−1n-1.

References

  1. [1]J.-P. Allouche and J. Shallit, The ring of \(k\)-regular sequences, Theoret. Comput. Sci. 98 (1992), 163–197. doi:10.1016/0304-3975(92)90001-V.DOI
  2. [2]D. Applegate, O. E. Pol, and N. J. A. Sloane, The toothpick sequence and other sequences from cellular automata, Congr. Numer. 206 (2010), 157–191. arXiv:1004.3036.arxiv.org/abs/1004.3036
  3. [3]S. Arora and B. Barak, Computational Complexity. A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090.
  4. [4]P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. R. Satti, and O. Weimann, Random access to grammar-compressed strings and trees, SIAM J. Comput. 44 (2015), 513–539. doi:10.1137/130936889.DOI
  5. [5]T. Neary and D. Woods, P-completeness of cellular automaton Rule 110, in Automata, Languages and Programming, ICALP 2006, Lecture Notes in Comput. Sci. 4051, Springer, 2006, 132–143.
  6. [6]P. Flajolet, X. Gourdon, and P. Dumas, Mellin transforms and asymptotics: Harmonic sums, Theoret. Comput. Sci. 144 (1995), 3–58. Author manuscript.DOI
  7. [7]OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, entries A139250, A161206, A161207, and A001316. Accessed November 15 and 16, 2026.

Paper details

vlnc:W_9f86v6bt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s ChatGPT 6 Astra

View statement
Looking for related papers…
Contents