pith. sign in

arxiv: 2604.06237 · v1 · submitted 2026-04-04 · 🧮 math.NT

On a perturbed Hofstadter Q-recursion

Benoit Cloitre This is my paper

Pith reviewed 2026-05-13 17:00 UTC · model grok-4.3

classification 🧮 math.NT
keywords Hofstadter Q-sequenceperturbed recurrencedyadic self-similarityCatalan numbersasymptotic boundnested recurrencearch structure
0
0 comments X

The pith

The perturbed Hofstadter sequence is defined for every positive integer and stays within O(1/sqrt(log n)) of n/2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a modified version of the Hofstadter Q-recurrence obtained by adding the alternating term (-1)^n at each step. This small change replaces the original sequence's potential for undefined terms with a fully defined sequence for all n. The modified sequence displays an exact dyadic self-similarity built from alternating arches whose combinatorial frequencies are counted by the Catalan numbers. From this structure the proof extracts the unconditional bound on the deviation from n/2.

Core claim

Adding the parity perturbation (-1)^n to the Hofstadter recurrence produces a sequence ~Q that is well-defined for every positive integer n. The values satisfy |~Q(n)/n - 1/2| = O(1/sqrt(log n)). The argument rests on the exact self-similar decomposition of the sequence into alternating arches whose frequencies are governed by the Catalan numbers.

What carries the argument

The parity-perturbed recurrence and its induced self-similar arch decomposition whose step counts follow the Catalan numbers.

If this is right

  • The perturbed sequence remains defined for all positive integers with no gaps in the recursion.
  • The ratio ~Q(n)/n approaches 1/2 at a rate no slower than a constant over the square root of log n.
  • Conditional on two minimal properties of the arch amplitudes the scaled deviation admits the explicit lim sup 1/(3 sqrt(2 pi)).
  • Numerical checks suggest the original Hofstadter sequence differs from the perturbed one by O(n/sqrt(log n)).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the conjectured difference bound between Q and ~Q holds then the original sequence would inherit the same closeness to n/2.
  • The arch decomposition may supply a template for proving existence in other nested recurrences that currently lack it.
  • Exact determination of the arch amplitudes would remove the remaining conjectural step from the refined asymptotic.

Load-bearing premise

The recursive construction never encounters an undefined predecessor because each arch completes before the next one begins.

What would settle it

Compute ~Q(n) up to n = 2^60 and verify whether |~Q(n)/n - 1/2| * sqrt(log n) remains bounded by a fixed constant.

Figures

Figures reproduced from arXiv: 2604.06237 by Benoit Cloitre.

Figure 1
Figure 1. Figure 1: Q(n)/n (red) and Qe(n)/n (blue), 1 ≤ n ≤ 7000. The parity split All values of Qe are odd (by induction on n, since Qe(n) is a sum of two past values plus (−1)n , and odd + odd ±1 is odd). Setting R(n) := (Qe(n) + 1)/2 and separating by parity of the index gives two subsequences A(m) := R(2m−1), B(m) := R(2m), (3) and the difference and symmetric modes σ(m) := A(m) + B(m) − m, δ(m) := B(m) − A(m). (4) Then … view at source ↗
Figure 2
Figure 2. Figure 2: δ(m) for 1 ≤ m ≤ 195. Positive arches (blue) alternate with negative arches (red). Black dots mark the zeros ur and vr. Define the amplitudes V +(r) := max ur≤m≤vr δ(m), V −(r) := max vr≤m≤ur+1 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: shows the excursion δ on the positive arch r = 2 (length 2a2 = 86). The symmetry δ(ur + t) = δ(vr − t) is exact. The excursion is a non-negative ±1 lattice path (a Dyck-type path) with a Cantor-like distribution of maxima. 0 10 20 30 40 50 60 70 80 t = m ur (arch r = 2, length 2a2 = 86) 0 2 4 6 8 10 12 14 (ur + t) V + = 15 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The excursion on the positive arch r = 3 (length 2a3 = 342). The sub-structure of level r = 2 is visible within the larger envelope. The palindromic symmetry of the excursion is a general property of balanced anti-palindromic words. Theorem 2.4. Let W be a binary word of length 2a, balanced (a zeros and a ones) and anti￾palindromic (W[k] + W[2a−1−k] = 1). Then hW (2a − t) = hW (t) for all 0 ≤ t ≤ 2a. Proof… view at source ↗
Figure 5
Figure 5. Figure 5: Left: V +(r), |V −(r)|, and 2ar on a log scale. All three grow as Θ(4r ), but the amplitudes are a factor O(1/ √ r) smaller than the arch lengths. Right: the ratio V +(r)/2ar decreases toward 0. The convergence proof reduces to inverting the counting function NA(x) = 2x + o(x). The following standard estimate suffices. Lemma 8.10. Let f : N → N be non-decreasing with ∆f ∈ {0, 1}, and let N(x) = #{m ≥ 1 : f… view at source ↗
Figure 6
Figure 6. Figure 6: Q(n) − Qe(n) for 1 ≤ n ≤ 200 000 with the envelope ± 0.70 · n/√ log n (dashed). The exact envelope constant Under Observations 9.4 and 9.10, the amplitude increments satisfy Wr = [PITH_FULL_IMAGE:figures/full_fig_p031_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The scaled fluctuation |Qe(n)/n − 1/2| p log2 n for 20 ≤ n ≤ 200 000. The dashed line marks 1/(3√ 2π) ≈ 0.133. The perturbed Conway–Mallows sequence The Conway–Mallows sequence a(n) = a(a(n−1)) + a(n−a(n−1)), a(1) = a(2) = 1 (A004001), satisfies a(n)/n → 1/2 [12]. The parity-perturbed variant b(n) = b(b(n−1)) + b(n−b(n−1)) + (−1)n , b(1) = b(2) = 1, exhibits a different behaviour. Numerical experiments up … view at source ↗
read the original abstract

The Hofstadter Q-sequence is a prominent example of nested recurrence. Despite decades of study, it is not even known whether Q(n) is defined for all n. Mantovanelli introduced a parity-perturbed variant $\widetilde{Q}$, obtained by adding $(-1)^n$ to the recursion, which surprisingly replaces the chaotic behaviour of Q by an exact dyadic self-similarity. In this paper we prove that $\widetilde{Q}$ is well-defined for all n and satisfies $|\widetilde{Q}(n)/n - 1/2| = O(1/\sqrt{\log n})$. The proof exploits the self-similar structure of the sequence, where alternating arches arise whose frequency combinatorics are governed by the Catalan numbers. A complementary analysis of the arch amplitudes, conditional on two minimal conjectural properties, refines the asymptotic formula to $\limsup_{n\to\infty} |\widetilde{Q}(n)/n - 1/2| \sqrt{\log_2 n} = 1/(3\sqrt{2\pi})$. Numerical experiments suggest the conjecture $Q(n) - \widetilde{Q}(n) = O(n/\sqrt{\log n})$, indicating that $\widetilde{Q}$ may serve as a tractable proxy for Q. This experimental direction will be investigated elsewhere.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that the parity-perturbed Hofstadter sequence ~Q, defined by adding (-1)^n to the standard Q-recursion, is well-defined for all n and satisfies the bound |~Q(n)/n − 1/2| = O(1/√log n). The argument proceeds by establishing an exact dyadic self-similarity in which alternating arches appear with frequencies counted by the Catalan numbers; the bound follows from a recursive decomposition of the deviation. A sharper limsup asymptotic is derived conditionally on two conjectures about arch amplitudes. Numerical experiments suggest that the difference between the original Q and ~Q is O(n/√log n).

Significance. This result is significant because it resolves the well-definedness question for a natural perturbation of the long-standing Hofstadter Q-sequence, whose own well-definedness remains open. The use of Catalan-number combinatorics to control the self-similar arches provides a clean, parameter-free derivation of the O(1/√log n) bound. The separation of the unconditional theorem from the conditional refinement is commendable. If the conjectures hold, the precise constant 1/(3√(2π)) would give a sharp description of the oscillation.

minor comments (2)
  1. The exact recursion and initial conditions for ~Q should be displayed explicitly in the introduction before the self-similarity argument is invoked.
  2. In the combinatorial analysis of arch frequencies, a short reminder of the Catalan-number identity employed would aid readers who are not specialists in the enumeration.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript. The report correctly captures the main contributions: the proof that the parity-perturbed sequence ~Q is well-defined for all n, the unconditional O(1/√log n) bound obtained from the exact dyadic self-similarity whose arch frequencies are counted by Catalan numbers, and the conditional refinement of the limsup constant. We also appreciate the acknowledgment that this resolves a natural perturbation of the still-open Hofstadter Q-sequence and the note on the experimental proxy relation. No specific major comments or criticisms appear in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The central proof proceeds by exhibiting an exact dyadic self-similarity of the perturbed recurrence, with alternating arches whose frequencies are enumerated by the standard Catalan numbers; the O(1/sqrt(log n)) bound is then extracted directly from the resulting recursive decomposition of the deviation. No parameters are fitted to the target quantity, no self-citations supply load-bearing uniqueness or ansatz, and the two conjectural arch-amplitude properties are explicitly quarantined to the sharper limsup statement. The derivation therefore rests on independent combinatorial facts rather than reducing to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on the combinatorial interpretation of arch frequencies via Catalan numbers and the assumption that the perturbed recurrence produces a unique integer sequence for every n; no free parameters are introduced for the main theorem.

axioms (2)
  • domain assumption The frequency combinatorics of the alternating arches are governed by the Catalan numbers
    Invoked to exploit the dyadic self-similarity of the perturbed sequence
  • standard math The perturbed recurrence defines a unique sequence for every positive integer n
    Basic well-definedness of recursive sequences with integer initial conditions

pith-pipeline@v0.9.0 · 5517 in / 1364 out tokens · 46320 ms · 2026-05-13T17:00:00.392659+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Alkan, N

    A. Alkan, N. Fox, and O.O. Aybar, On Hofstadter heart sequences,Complexity(2017), Article ID 2614163

    work page 2017

  2. [2]

    Alkan, On a conjecture about generalizedQ-recurrence,Open Math.16(2018), 1490– 1500

    A. Alkan, On a conjecture about generalizedQ-recurrence,Open Math.16(2018), 1490– 1500

    work page 2018

  3. [3]

    Balamohan, A

    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

    work page 2007

  4. [4]

    Cloitre and J

    J.M. Campbell and B. Cloitre, Meta-automatic sequences, arXiv:2602.23395, 2026

    work page arXiv 2026

  5. [5]

    Dekking, On Hofstadter’s married functions,Fibonacci Quart.61(2023), 199–211

    F.M. Dekking, On Hofstadter’s married functions,Fibonacci Quart.61(2023), 199–211

    work page 2023

  6. [6]

    Fox,An Exploration of Nested Recurrences Using Experimental Mathematics, Ph.D

    N. Fox,An Exploration of Nested Recurrences Using Experimental Mathematics, Ph.D. the- sis, Rutgers University, 2017

    work page 2017

  7. [7]

    Grytczuk, Another variation on Conway’s recursive sequence,Discrete Math.282(2004), 149–161

    J. Grytczuk, Another variation on Conway’s recursive sequence,Discrete Math.282(2004), 149–161

    work page 2004

  8. [8]

    Hofstadter,Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, New York, 1979

    D.R. Hofstadter,Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, New York, 1979

    work page 1979

  9. [9]

    Jackson and F

    D.M. Jackson and F. Ruskey, Meta-Fibonacci sequences, binary trees, and extremal compact codes,Electron. J. Combin.13(2006), #R26

    work page 2006

  10. [10]

    T.KuboandR.Vakil, OnConway’srecursivesequence,Discrete Math.152(1996), 225–252

    work page 1996

  11. [11]

    Letouzey, S

    P. Letouzey, S. Li, and W. Steiner,Generalized Hofstadter functions: geometric representa- tions and numeration systems, arXiv:2410.07063, 2024

    work page arXiv 2024

  12. [12]

    Mallows, Conway’s challenge sequence,Amer

    C.L. Mallows, Conway’s challenge sequence,Amer. Math. Monthly98(1991), 5–20

    work page 1991

  13. [13]

    Mantovanelli,Dyadic self-similarity in a perturbed HofstadterQ-recursion, arXiv:2603.16111, 2026

    M. Mantovanelli,Dyadic self-similarity in a perturbed HofstadterQ-recursion, arXiv:2603.16111, 2026

    work page arXiv 2026

  14. [14]

    J.Shallit,The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut, London Math. Soc. Lecture Note Series 482, Cambridge University Press, 2022. 33

    work page 2022