Re-Ordering the Generalized Hofstadter Functions G, H, and Beyond
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). In a previous article, we proved that this family is ordered pointwise: for all k and n, we have F_k(n) ≤ F_{k+1}(n)$. Here we propose a much shorter proof of this theorem, without infinite morphic words. The key ingredient for this direct proof is a new formula expressing iterates of the preimages of F_k . Thanks to this formula, we also prove several conjectures mentioned in our previous article. In particular we obtain that F_k(n) < F_{k+1}(n) when n > (k + 1)(k + 6)/2. We provide a certified formalization of all these results in the Rocq proof assistant.
Related
- Rhaly and generalized Hilbert operators between spaces of analytic functions
- Generalized p-ary cPS Bent Functions
- The non-spherical sup-norm problem for GL(n) and generalized spherical functions
- Generalized functions in a Non-Archimedean field
- Higher order Teodorescu transform in the theory of generalized partial-slice monogenic functions
BibTeX
@misc{letouzey2026reordering,
title = {{Re-Ordering the Generalized Hofstadter Functions G, H, and Beyond}},
author = {Pierre Letouzey},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35994},
eprint = {2610.35994},
archivePrefix = {arXiv},
url = {https://inria.hal.science/hal-05839193v1},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Re-Ordering the Generalized Hofstadter Functions G, H, and Beyond
AU - Pierre Letouzey
PY - 2026
DA - 2026/10/26
PB - HAL
DO - 10.48550/arxiv.2610.35994
UR - https://inria.hal.science/hal-05839193v1
AB - 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). In a previous article, we proved that this family is ordered pointwise: for all k and n, we have F_k(n) ≤ F_{k+1}(n)$. Here we propose a much shorter proof of this theorem, without infinite morphic words. The key ingredient for this direct proof is a new formula expressing iterates of the preimages of F_k . Thanks to this formula, we also prove several conjectures mentioned in our previous article. In particular we obtain that F_k(n) < F_{k+1}(n) when n > (k + 1)(k + 6)/2. We provide a certified formalization of all these results in the Rocq proof assistant.
ER -