← 研踪 PaperTrailarXiv:2610.35994 · v1
Re-Ordering the Generalized Hofstadter Functions G, H, and Beyond
首次提交 2026-10-26 20:55
版本更新 2026-10-26 20:55
雷达观测 2026-10-29 00:36
摘要
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) $le$ 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-26 20:55 · 最新观测版本
Re-Ordering the Generalized Hofstadter Functions G, H, and Beyond
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) $le$ 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.
查看此版本解读 →查看此版本原文 ↗