On a perturbed Hofstadter $Q$-recursion
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917388955418624 |
|---|---|
| author | Cloitre, Benoit |
| author_facet | Cloitre, Benoit |
| contents | 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π})$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06237 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On a perturbed Hofstadter $Q$-recursion Cloitre, Benoit Number Theory 11B37 (primary), 05A16, 68R15 (secondary) 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π})$. 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. |
| title | On a perturbed Hofstadter $Q$-recursion |
| topic | Number Theory 11B37 (primary), 05A16, 68R15 (secondary) |
| url | https://arxiv.org/abs/2604.06237 |