Abstract:Hofstadter's G function is recursively defined via $G(0)=0$ and then $G(n)=n-G(G(n-1))$. Following Hofstadter, we vary the number $k$ of nested recursive calls in this equation and obtain a family of functions $(F\_k)$. Here we establish that this family is ordered pointwise: for all $k$ and $n$, we have $F\_k(n) \le F\_{k+1}(n)$. To achieve this, we make a detour via infinite morphic words generalizing the Fibonacci word. We prove various properties of these words, concerning the lengths of substituted prefixes of these words and the number of occurrences of specific letters in these prefixes. We also relate the limits of $\frac{1}{n}F\_k(n)$ to the frequencies of letters in the considered words. We provide a certified formalization of all these results in the Rocq proof assistant.
| Subjects: | Discrete Mathematics (cs.DM); Formal Languages and Automata Theory (cs.FL); Combinatorics (math.CO); Number Theory (math.NT) |
| Cite as: | arXiv:2410.00529 [cs.DM] |
| (or arXiv:2410.00529v2 [cs.DM] for this version) | |
| https://doi.org/10.48550/arXiv.2410.00529 arXiv-issued DOI via DataCite |
|
| Journal reference: | Journal of Integer Sequences, 2026, 29 (3), pp.26.3.3 |
From: Pierre Letouzey [view email] [via CCSD proxy]
[v1]
Tue, 1 Oct 2024 09:15:10 UTC (23 KB)
[v2]
Fri, 22 May 2026 14:41:34 UTC (27 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。