betaFeedback

WorksMathematics

An Odd-Arch Family of Perturbed Hofstadter Q-Recursions: Gaussian Profiles and Exact Frequency Laws

Abstract

For every integer p≥2p\ge2, we construct a globally well-defined positive odd sequence QpQ_p satisfying, after an explicit finite initial block, Qp(n)=Qp(n−Qp(n−1))+Qp(n−Qp(n−2))−(−1)nQ_p(n)=Q_p(n-Q_p(n-1))+Q_p(n-Q_p(n-2))-(-1)^n. Its binary block words admit the exact factorization Up,k=(AkA‾k+1)p−1Ak+2U_{p,k}=(A_k\overline{A}_{k+1})^{p-1}A_{k+2}, producing exactly 2p−12p-1 alternating signed arches per natural block. The elementary word heights converge uniformly to the Gaussian isoperimetric profile φ∘Φ−1φ\circΦ^{-1}. For each fixed pp, this yields an explicit dyadic limiting profile with 2p−12p-1 sign transitions and a sharp relative-error constant Λp=bp/2Λ_p=b_p/2, where bpb_p is determined by bp((3p−1)/2+Φ(−bp))=φ(bp)b_p((3p-1)/2+Φ(-b_p))=φ(b_p). We determine all zeros and parity crossings in sufficiently large dyadic blocks. For p≥3p\ge3, there are exactly 2p−12p-1 transverse even-index zeros, whereas the three-arch case p=2p=2 exhibits an alternating four/six-zero pattern. An ordered frequency factorization gives exact dyadic histograms, moments, total-variation distances, and extremal multiplicities. The limiting frequency generating function z3/(2−z)z^3/(2-z) is universal, although the highest finite multiplicities depend on pp. Finally, the summatory function has main terms N2/4+(N/2)log⁡2NN^2/4+(N/2)\log_2N, an explicit parameter-dependent log-periodic term of order NN, and remainder Op(N/log⁡N)O_p(N/\sqrt{\log N}).

Supplementary material. Reproducibility archive: 10.5281/zenodo.23593788.

Introduction and main results

Changing a finite initial block in a nested recurrence changes which parts of the past are read, not merely the first few values. Here this mechanism produces an explicit family QpQ_p, indexed by integers p≥2p \ge2, with any prescribed odd number 2p−12p-1 of signed excursions per natural scale. All members use the same recurrence; the parameter enters only through the initial block. Their elementary excursions have a common Gaussian limit, while their arrangement, finite transitions, and upper value multiplicities depend on the parameter.

The family and its global structure

Write

np={8,p=2,6p−6,p≥3.n_p = \begin{cases} 8, & p=2,\\ 6p-6, & p\ge3. \end{cases}

We prescribe every value Qp(n)Q_p(n) for 1≤n<np1 \le n < n_p and then apply

Qp(n)=Qp(n−Qp(n−1))+Qp(n−Qp(n−2))−(−1)n,n≥np.(1)Q_p(n)=Q_p\left(n-Q_p(n-1)\right)+Q_p\left(n-Q_p(n-2)\right)-(-1)^n,\qquad n\ge n_p. \tag*{(1)}

For p=2p=2 the prescribed block is (1,1,3,3,3,3,5)(1,1,3,3,3,3,5). The three-arch member Q2Q_2 is recorded in the On-Line Encyclopedia of Integer Sequences as A401334 [10]. For p≥3p\ge3, put m=⌈n/2⌉m=\lceil n/2\rceil and prescribe, for 1≤n≤6p−71\le n\le6p-7,

Qp(n)={2min⁡(m−1,p−1)+1,m<p+2,2p+2⌈(m−p−2)/2⌉+1,m≥p+2, n odd,2p+2⌊(m−p−2)/2⌋+1,m≥p+2, n even.(2)Q_p(n)= \begin{cases} 2\min(m-1,p-1)+1, & m<p+2,\\ 2p+2\left\lceil(m-p-2)/2\right\rceil+1, & m\ge p+2,\ n\text{ odd},\\ 2p+2\left\lfloor(m-p-2)/2\right\rfloor+1, & m\ge p+2,\ n\text{ even}. \end{cases} \tag*{(2)}

The entire block is part of the definition: the recurrence must not be applied before npn_p. Each recursive argument must belong to {1,…,n−1}\{1,\ldots,n-1\}; no values at zero or at negative indices are supplied.

Theorem 1.1 (Global odd-arch family). For every integer p≥2p\ge2, the initial block above and (1) determine a unique sequence for all positive indices. All values are odd, and

1≤Qp(n)≤n,Qp(n+2)−Qp(n)∈{0,2}(n≥1).(3)1\le Q_p(n)\le n,\qquad Q_p(n+2)-Q_p(n)\in\{0,2\}\qquad(n\ge1). \tag*{(3)}

Each parity subsequence assumes every positive odd value, each only finitely often. The independently constructed block words satisfy

Up,k=(AkA‾k+1)p−1Ak+2(k≥2),(4)U_{p,k}=(A_k\overline{A}_{k+1})^{p-1}A_{k+2}\qquad(k\ge2), \tag*{(4)}

where the primitive Dyck words AkA_k are defined in (9) and have length ℓk=(2k+2(−1)k)/3\ell_k=(2^k+2(-1)^k)/3. A bar is bitwise complementation, not reversal. Consequently each natural block has exactly 2p−12p-1 primitive signed excursions, with asymptotic relative lengths 1,2,…,1,2,41,2,\ldots,1,2,4.

The proof in § 3 constructs the words and two slow cores before checking any nested identity. In particular, existence is not assumed in order to establish the block structure. The first three members are the three-, five-, and seven-arch sequences Q2Q_2, Q3Q_3, Q4Q_4:

MemberPrescribed initial blockRecursion starts at
Q2Q_2(1,1,3,3,3,3,5)(1,1,3,3,3,3,5)8
Q3Q_3(1,1,3,3,5,5,5,5,7,7,9)(1,1,3,3,5,5,5,5,7,7,9)12
Q4Q_4(1,1,3,3,5,5,7,7,7,7,9,9,11,9,11,11,13)(1,1,3,3,5,5,7,7,7,7,9,9,11,9,11,11,13)18

Table 3.

Shape, finite transitions, frequencies, and summation

The common elementary profile is

J(x)=φ(Φ−1(x)),0<x<1,J(0)=J(1)=0,J(x)=\varphi\left(\Phi^{-1}(x)\right),\qquad0<x<1,\qquad J(0)=J(1)=0,

where φ\varphi and Φ\Phi are the standard normal density and distribution function. § 4 proves uniform convergence of the normalized elementary heights. § 5 combines these limits at the exact block positions and obtains an explicit standard dyadic profile PpP_p. For each fixed pp and index parity rr,

(−1)j+rpj(Qp(n)n−12)⟶Pp(n/2j)(-1)^{j+rp}\sqrt{j}\left(\frac{Q_p(n)}{n}-\frac{1}{2}\right)\longrightarrow P_p(n/2^j)

uniformly on 2j≤n≤2j+12^j\le n\le2^{j+1} along that parity, in the precise sampling convention of Theorem 5.1. There are exactly 2p−12p-1 limiting sign transitions. The sharp envelope is

lim sup⁡n→∞log⁡2n∣Qp(n)n−12∣=Λp=bp2,bp(3p−12+Φ(−bp))=φ(bp),\limsup_{n\to\infty}\sqrt{\log_2 n}\left|\frac{Q_p(n)}{n}-\frac{1}{2}\right|=\Lambda_p=\frac{b_p}{2},\qquad b_p\left(\frac{3p-1}{2}+\Phi(-b_p)\right)=\varphi(b_p),

with a unique positive root bpb_p. In particular, Λp∼1/(3p2π)\Lambda_p\sim1/(3p\sqrt{2\pi}) as p→∞p\to\infty. This last assertion concerns the constants after the fixed-pp limit; no simultaneous limit in pp and nn is asserted.

The finite structure contains more information than the profile alone. § 6 gives exact finite zero and crossing tables. For p≥3p\ge3 and j≥p+⌊log⁡2p⌋+10j\ge p+\lfloor\log_2p\rfloor+10, the jj-th standard block has exactly 2p−12p-1 even-index zeros, all transverse. The four/six-zero alternation at p=2p=2 is a genuine exceptional feature, not a universal rule.

For νp(v)=#{n≥1:Qp(n)=v}\nu_p(v)=\#\{n\ge1:Q_p(n)=v\}, define

Dp,j(z)=∑u=2j2j+1−1zνp(2u+1).D_{p,j}(z)=\sum_{u=2^j}^{2^{j+1}-1}z^{\nu_p(2u+1)}.

§ 7 derives both the ordered frequency words and their histograms. The normalized limit is always z3/(2−z)z^3/(2-z), but the finite upper tail changes with pp. With d=⌊log⁡2p⌋d=\lfloor\log_2p\rfloor, the exact moments on j≥d+2j\ge d+2 are

EXp,j=4−2−j,Var⁡(Xp,j)=2−(2(j−d)+4p−5)2−j−4−j.\mathbb{E}X_{p,j}=4-2^{-j},\qquad\operatorname{Var}(X_{p,j})=2-\left(2(j-d)+4p-5\right)2^{-j}-4^{-j}.

Theorem 7.5 gives all coefficients, split according to whether pp is a power of two. The following results determine exact total-variation distances and every location of the two highest multiplicities. A worked p=3p=3 example makes the join correction and the dyadic cuts explicit before the general histogram formulas.

Finally, § 8 proves an exact telescoping identity and, with Cp=2(3p+1)/3C_p=2(3p+1)/3,

∑n≤NQp(n)=N24+N2log⁡2N+NΨp({log⁡2(N/Cp)})+Op(Nlog⁡N).\sum_{n\le N}Q_p(n)=\frac{N^2}{4}+\frac{N}{2}\log_2N+N\Psi_p(\{\log_2(N/C_p)\})+O_p\left(\frac{N}{\sqrt{\log N}}\right).

where Ψp(θ)=p−1−12log⁡2Cp−θ2−2−θ\Psi_p(\theta)=p-1-\frac{1}{2}\log_2C_p-\frac{\theta}{2}-2^{-\theta} on [0,1][0,1], extended continuously with period one. Thus the logarithmic bias and the periodic shape are shared by the family, while the phase scale and vertical constant are explicit functions of pp.

Context and organization

Hofstadter introduced the unperturbed QQ-recursion in Gödel, Escher, Bach [4]. For related nested recurrences, explicit combinatorial descriptions have often supplied the missing control of the self-referential arguments. Tanny [11] analyzed a monotone relative; Balamohan, Kuznetsov, and Tanny [1] obtained a complete description of another variant through its generations and value frequencies. Tree representations provide a further source of exact solutions [5]. These examples suggest looking for a finite combinatorial evolution behind the numerical sequence.

The original parity-perturbed recursion was introduced by the present author [6] and is recorded as OEIS A394051 [9]. It starts with (1,1)(1,1) and adds +(−1)n+(-1)^n to the two nested terms. Cloitre [3] proved its global definedness and the optimal error order n/log⁡nn/\sqrt{\log n} by an exact-fit interleaving construction, binary heights, and canonical plane forests. The same framework led to a dyadic frequency law [6]. A subsequent analysis of the associated two-variable zeta function identified a periodic summatory term and a weak Gaussian limit for a distinguished family of layers [7].

A related delayed perturbation admits uniform Gaussian profiles through nonlinear averaging and smooth comparison functions [8]. Here the elementary lengths alternate between 2L+22L+2 and 2L−22L-2. An exact change of coordinates removes both the length correction and the additive height term, allowing that comparison method to treat the two maps within one identity.

Our construction uses Cloitre’s exact-fit framework. In particular, the tape counters and height additivity come from [3 Definition 2.3 and Lemmas 2.4–2.5], and the parked-head verification follows [3 Lemmas 3.3–3.4]. On Dyck inputs, S+S_+ agrees with Cloitre’s transform TT; if P=0R1P=0R1 is primitive Dyck, then S−(P)=T(R)S_-(P)=T(R) [3 Section 4.1]. The elementary excursions are inherited. The contribution here is their repeated signed-pair organization, its explicit finite seeds and block positions, and the resulting parameter-dependent shape, crossing, frequency, and summation laws. § 9 gives the exact identification with the original word family and separates the inherited tools from these results.

The main text develops the general parameter pp throughout. Appendix § 11 records the detailed p=2p=2 formulas, including its exceptional tangencies, pure valuation histogram, and worked finite crossing example. This retains the three-arch model as an explicit specialization rather than as a prerequisite for the familial construction.

Figure 1. The three explicit limiting standard-block profiles for p=2,3,4p=2,3,4. The same elementary Gaussian function produces distinct arrangements and different sharp amplitudes.

Causal word maps and elementary excursions

For a binary word PP of length LL, let oP(t)o_P(t) and zP(t)z_P(t) count ones and zeros in its prefix of length tt, and let

References

  1. [1]B. Balamohan, A. Kuznetsov, and S. Tanny, On the behavior of a variant of Hofstadter’s Q-sequence, J. Integer Seq. 10 (2007), Article 07.7.1. https://cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.html.
  2. [3]B. Cloitre, The Mantovanelli–Hofstadter Sequence, arXiv:2604.06237v3 [math.NT] (2026). https://arxiv.org/abs/2604.06237v3.
  3. [4]D. R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, New York, 1979.
  4. [5]B. Jackson and F. Ruskey, Meta-Fibonacci sequences, binary trees and extremal compact codes, Electron. J. Combin. 13 (2006), Research Paper 26. doi:10.37236/1052.DOI
  5. [6]M. Mantovanelli, A Dyadic Frequency Law for a Perturbed Hofstadter Q-Recursion, arXiv:2603.16111v3 [math.CO] (2026). https://arxiv.org/abs/2603.16111v3.
  6. [7]M. Mantovanelli, A Two-Variable Zeta Function for a Parity-Perturbed Hofstadter Q-Recursion: The Exceptional t = −1 Slice and Gaussian Boundary Layers, arXiv:2609.02412 [math.NT] (2026). https://arxiv.org/abs/2609.02412.
  7. [8]M. Mantovanelli, A New Perturbed Hofstadter Q-Recursion: Exact Frequencies and Gaussian Profiles, ResearchGate preprint (2026). doi:10.13140/RG.2.2.36783.70561. Reproducibility archive: doi:10.5281/zenodo.23426341.DOI
  8. [9]The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, entry A394051, accessed 17 October 2026. https://oeis.org/A394051.
  9. [10]The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, entry A401334 (2026). https://oeis.org/A401334.
  10. [11]S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discrete Math. 105 (1992), 227–239. doi:10.1016/0012-365X(92)90145-6.DOI
  11. [12]M. Mantovanelli, An Odd-Arch Family of Perturbed Hofstadter Q-Recursions: Gaussian Profiles and Exact Frequency Laws (Reproducibility Archive), Zenodo (2026). doi:10.5281/zenodo.23593788.

Paper details

vlnc:W_tr2ujhyu
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

Not recorded for this paper

View statement
Looking for related papers…
Contents