The Hofstadter consecutive-sum sequence omits infinitely many positive integers

本文证明了由 $a_1=1, a_2=2$ 及后续取为能表示为至少两个连续先前项之和的最小整数所定义的贪心自生成序列，其增长阶介于 $n+\omega(1)$ 与 $n^{4175/2506+o(1)}$ 之间，从而证实了该序列遗漏了无穷多个正整数并解决了 OEIS A005243 条目中的猜想。

要点

这是一篇关于数学序列的论文，作者全宇（Quanyu Tang）解决了一个困扰数学家多年的谜题。为了让你轻松理解，我们可以把这个数学问题想象成**“一个贪心的数字收集游戏”**。

1. 游戏规则：贪心的“数字收集者”

想象你有一个数字收集器，它非常贪心，而且只喜欢连续的数字。

• 初始状态：游戏开始时有两个数字：1 和 2。
• 收集规则：
  1. 收集器会查看之前已经收集到的所有数字。
  2. 它尝试把连续的一段数字加起来（比如 1+2，或者 2+3，但不能是 1+3，因为中间缺了 2）。
  3. 它会把所有能算出来的和，按从小到大的顺序排好。
  4. 关键一步：它总是选择比当前最后一个数字大的最小那个和，作为下一个新数字加入序列。

让我们玩几轮看看：

• 已有：1, 2
• 可能的和：1+2=3。
• 下一个数字是 3（因为它比 2 大，且是最小的可能和）。
• 已有：1, 2, 3
• 可能的和：1+2=3（已有），2+3=5，1+2+3=6。
• 下一个数字是 5（因为 4 无法由连续数字相加得到，而 5 可以）。
• 已有：1, 2, 3, 5
• 可能的和：3+5=8，2+3+5=10...
• 下一个数字是 6（等等，1+2+3=6 也是可能的，且比 5 大，比 8 小）。

于是，这个序列变成了：1, 2, 3, 5, 6, 8, 10, 11, 14...

2. 核心问题：它会漏掉数字吗？

如果你盯着这个序列看，你会发现它似乎“吞掉”了大部分数字，但总有一些数字凭空消失了。
比如：4 不见了，7 不见了，9 不见了，12 也不见了。

霍夫施塔特（Hofstadter）提出的问题是：

这个序列最终会“填满”所有正整数吗？还是会永远漏掉无穷多个数字？

在数学界，大家猜测它会漏掉无穷多个数字，但没人能证明。这就好比你在玩一个填坑游戏，大家觉得坑永远填不满，但没人能拿出确凿的证据说“看，这里永远会有空位”。

3. 作者的发现：两个重大突破

全宇在这篇论文中，用两种不同的方法彻底解决了这个问题。

突破一：定性证明（它确实漏掉了无穷多个数字）

作者证明了这个序列不仅漏掉数字，而且漏掉的数量会越来越多，永远填不满。

• 通俗比喻：
  想象这个序列是一条正在生长的藤蔓。如果它长得太快，把每个数字都占满，那它应该像 1, 2, 3, 4, 5... 这样，第 $n$ 个数字就是 $n$。
  但作者发现，这个序列的第 $n$ 个数字，实际上比 $n$ 要大得多！
  公式是：$a_n = n + \text{一个越来越大的数}$。
  这意味着，随着序列变长，它“跳过”的数字（空隙）会越来越多。就像藤蔓长得太茂盛，把下面的土壤都盖住了，导致很多数字根本进不去。
  结论：这个序列确实漏掉了无穷多个正整数。这解决了 OEIS 数据库（一个著名的整数序列百科全书）里的一个长期猜想。

突破二：定量证明（它长得有多快？）

既然它漏掉了数字，那它到底长得有多快？是像火箭一样指数级爆炸，还是像树一样多项式增长？

作者给出了一个非常精确的上限。

• 通俗比喻：
  以前我们不知道这个序列能跑多快，可能以为它会像光速一样飞。
  作者证明：虽然它跑得比 1, 2, 3... 快，但它不会无限加速。它的增长速度被限制在一个“多项式”的范围内（类似于 $n$ 的 1.66 次方左右）。
  这就像给这匹狂奔的野马套上了缰绳，告诉它：“你虽然跑得快，但你不可能超过这个速度极限。”

4. 作者是怎么做到的？（简单的数学魔法）

作者用了两个很巧妙的工具：

1. 关于“2 的幂”的陷阱：
   作者发现，如果这个序列真的能填满所有数字（即没有空隙），那么它必须能生成所有的"2 的幂”（如 4, 8, 16, 32...）。
   但是，数学上有一个定理说：某些特定的方程（涉及平方和 2 的幂）只有有限个解。
   作者通过逻辑推理发现：如果序列没有空隙，就会制造出无限多个这样的解，这与定理矛盾。
   结论：假设不成立，所以序列必须有空隙。

2. 凸集与差集（像拼图一样）：
   为了计算它长得有多快，作者把这个问题转化成了“拼图”问题。
   他把序列的前缀和看作一个形状特殊的集合（凸集）。数学界最近有一个关于这种集合“差集”（两个数相减能产生多少种结果）的新定理。
   作者利用这个新定理，计算出这个序列能产生的“和”的数量，从而反推出序列本身的增长速度上限。

5. 总结与意义

• 解决了什么：证明了霍夫施塔特序列会漏掉无穷多个数字，并给出了它增长速度的数学上限。
• 为什么重要：
  • 它解决了一个经典的数学猜想。
  • 它展示了如何将看似简单的“数字游戏”与高深的数论（如丢番图方程）和组合数学（如凸集理论）联系起来。
• 未来的谜题：
  虽然作者证明了它漏掉数字，但漏掉的具体规律是什么？作者通过计算机模拟发现，漏掉的数量似乎遵循某种“立方根”或“平方根”的规律，但这还需要未来的数学家去进一步探索。

一句话总结：
这篇论文告诉我们，那个贪心的数字收集器，无论怎么努力，都永远无法填满所有的数字坑洞，而且它奔跑的速度虽然快，但也是有迹可循的。

技术摘要

这是一份关于唐全宇（Quanyu Tang）论文《Hofstadter 连续和序列遗漏无限多个正整数》（The Hofstadter Consecutive-Sum Sequence Omits Infinitely Many Positive Integers）的详细技术总结。

1. 研究背景与问题 (Problem)

核心对象：
论文研究的是由 R. Hofstadter 提出的一个贪心自生成序列（Greedy Self-Generating Sequence），记为 $(a_n)_{n \ge 1}$。

• 定义：$a_1 = 1, a_2 = 2$。对于 $k \ge 3$，$a_k$ 定义为大于 $a_{k-1}$ 的最小整数，且该整数可以表示为至少两个连续的先前项之和。
  即：$a_k = \sum_{i=p}^q a_i$，其中 $1 \le p \le q \le k-1$且$q-p \ge 1$。
• OEIS 编号：A005243。
• 初始项：1, 2, 3, 5, 6, 8, 10, 11, 14, 16, 17, 18, 19, 21, 22, 24, 25, 29, 30, 32, ...
• 缺失项：序列已经遗漏了 4, 7, 9, 12, 13, 15, 20 等数字。

核心问题：
Hofstadter 曾询问该序列的渐近行为。具体而言，OEIS 条目 A005243 中提出了一个猜想（Conjecture 1.2）：

猜想：该序列 $(a_n)$ 遗漏了无限多个正整数。

换言之，序列的增长速度是否严格快于线性增长（即 $a_n - n \to \infty$）？

2. 主要贡献与结果 (Key Contributions & Results)

本文彻底解决了上述猜想，并给出了定量的上界估计。

2.1 定性结果：无限遗漏 (Qualitative Result)

定理 1.4 & 推论 1.5：

• 对于任意长度 $s \ge 2$ 的正整数初始种子 $u$，定义广义序列 $(a_n^u)$。
• 令 $b_n = a_n - n$。论文证明了序列 $(b_n)$ 是无界的（unbounded），且对于 $n \ge s$ 是非递减的。
• 结论：$a_n = n + \omega(1)$。这意味着 $a_n - n \to \infty$。
• 推论：序列 $(a_n)$ 遗漏了无限多个正整数。这直接证实了 OEIS 中的猜想 1.2。

2.2 定量结果：多项式上界 (Quantitative Upper Bound)

定理 1.6：

• 对于经典序列 $(1, 2)$，论文给出了 $a_n$ 的增长上界。
• 对于任意 $\varepsilon > 0$，存在常数 $C_\varepsilon$ 使得：
  $$a_n \le C_\varepsilon n^{\frac{4175}{2506} + \varepsilon}$$
• 指数 $\frac{4175}{2506} \approx 1.666$。这是该序列增长速率的第一个多项式上界。

3. 方法论 (Methodology)

论文采用了组合数论、丢番图方程和加性组合学（Additive Combinatorics）相结合的方法。

3.1 定性证明策略：反证法与 Schinzel-Tijdeman 定理

1. 单调性分析：首先证明 $b_n = a_n - n$ 是非递减的。
2. 反证假设：假设 $b_n$ 有界，则存在 $N_0$ 和常数 $B$，使得当 $n \ge N_0$ 时，$a_n = n + B$（即序列尾部呈线性）。
3. 结构分析：
   • 如果尾部是线性的，那么足够大的 $2^r$（2 的幂次）必须出现在序列中（因为$a_n$ 会覆盖所有非 2 的幂次的和，而 2 的幂次无法表示为连续整数和，除非序列本身包含它们）。
   • 分析 $2^r$作为连续项之和的表示形式。利用线性尾部的假设，推导出$2^r$必须满足形如$2^{r+1} = v^2 + v + E$的方程，其中$E$ 来自有限集合。
4. 矛盾导出：
   • 利用 Schinzel-Tijdeman 定理 的一个推论（关于方程 $y^k = P(x)$ 的整数解有限性）。
   • 方程 $v^2 + v + E = 2^k$ 对于固定的 $E$ 只有有限个整数解 $(v, k)$（当 $k > 2$）。
   • 然而，如果 $b_n$ 有界，则会有无限多个 $r$ 使得 $2^r$ 在序列中，从而产生无限多组解，这与 Schinzel-Tijdeman 定理矛盾。
   • 结论：假设不成立，$b_n$ 必须无界。

3.2 定量证明策略：凸集差集与贪心枚举

1. 贪心枚举性质：证明序列 $(a_n)$ 实际上就是所有“可表示为至少两个连续项之和的整数”的递增枚举。
2. 前缀和集合的凸性：
   • 定义前缀和 $s_m = \sum_{i=1}^m a_i$。
   • 证明集合 $\mathcal{S}_m = \{s_0, s_1, \dots, s_m\}$ 是一个凸集（Consecutive differences are strictly increasing）。
3. 差集与可表示数的关系：
   • 连续项之和可以表示为前缀和的差：$\sum_{i=p}^q a_i = s_q - s_{p-1}$。
   • 因此，可表示数的集合 $R_m$ 包含在差集 $\mathcal{S}_m - \mathcal{S}_m$ 中。
4. 应用 Bloom 的界限：
   • 引用 Bloom (2023) 关于有限凸集差集大小的下界定理：对于凸集 $A$， $|A - A| \ge c |A|^{6681/4175 - \eta}$。
   • 将此应用于 $\mathcal{S}_m$，得到可表示数的数量 $|R_m|$ 的下界约为 $m^{6681/4175}$。
5. 递归迭代：
   • 利用贪心性质：如果 $[1, X]$ 中有 $N$ 个可表示数，则 $a_{N+2} \le X$。
   • 结合 $|R_m|$ 的下界，建立 $a_n$ 的递归不等式：$a_n \lesssim n^{1/\delta} a_{n^{1/\delta}}$，其中 $\delta = 6681/4175$。
   • 通过迭代该递归关系，最终推导出 $a_n \ll n^{\frac{1}{\delta-1} + \varepsilon}$。
   • 计算指数：$\frac{1}{\delta - 1} = \frac{1}{\frac{6681}{4175} - 1} = \frac{4175}{2506}$。

4. 数值观察与讨论 (Numerical Observations)

• 作者计算了 $n$ 高达 30,000 的数值。
• 定义 $b_n = a_n - n$。
• 数据表明 $b_n$ 的增长速度介于 $n^{1/5}$ 和 $n^{1/2}$ 之间。
• 拟合曲线 $b_n / n^{1/3}$ 在计算范围内看起来相对平坦，暗示真实的增长指数 $\alpha$ 可能接近 $1/3$（即$a_n \approx n + n^{1/3}$）。
• 目前的理论上界 $n^{1.666}$ 远大于数值观察到的线性增长趋势，表明该上界并非紧确（tight），但它是目前唯一的解析上界。

5. 意义 (Significance)

1. 解决长期猜想：首次严格证明了 Hofstadter 连续和序列遗漏无限多个整数，解决了 OEIS A005243 中的核心猜想。
2. 推广性：证明方法不仅适用于种子 $(1, 2)$，还适用于任意正整数种子，展示了该现象的普遍性。
3. 连接不同领域：巧妙地将贪心序列的构造问题转化为丢番图方程（Schinzel-Tijdeman）和加性组合学（凸集差集）问题，展示了现代数论工具在解决经典序列问题中的威力。
4. 提供上界：给出了该序列增长速率的第一个多项式上界，为后续研究提供了基准。尽管上界较松，但它证明了序列具有多项式增长而非指数增长。

总结：
这篇论文通过深刻的数论分析，证明了 Hofstadter 序列虽然看似密集，但实际上“稀疏”到足以遗漏无限多个整数，并给出了其增长速率的严格上界。这项工作不仅解决了具体的 OEIS 猜想，也为研究自生成序列的渐近行为提供了新的理论框架。