下载客户端

一个名叫Collatz猜想的未解难题

2025-08-29 15:23

来源：澎湃新闻·澎湃号·湃客

Collatz 猜想指出，如果你选择一个正整数，如果它是偶数，就将其除以2，如果它是奇数，就将其乘以3并加上1，最终都会得到1。

作者：Sophie Maclean（伦敦国王学院解析数论在读博士生）2025-8-27

译者：zzllrr小乐（数学科普公众号）2025-8-28

我要你选一个正整数。任意一个都可以——你可以自由选择。如果你选的是奇数，就把它乘以 3，再加 1。如果是偶数，就把它减半。取得结果并重复这个过程。实际上，我想让你一直重复，直到你陷入循环。

例如，如果你的数字是 7，你首先要乘以 3，再加 1，得到 22。现在你得到的是一个偶数，所以你需要将其减半得到 11。11 是奇数，而 3 × 11 + 1 = 34。然后这个模式会继续下去……

11 → (×3 + 1) → 34 → (÷ 2) → 17 → (×3 + 1) → 52 → (÷ 2) → 26 → (÷ 2) → 13 → (×3 + 1) → ...

事实证明，用箭头表示是一种非常有用的符号。我们可以将 11 的路径表示为 11 → 34 → 17 → 52 → 26 → 13 →……

现在轮到你了。选一个你自己的数字，然后按照算法走，直到你发现自己陷入了循环。完成了吗？

好的。

首先我要说的是，我无法从数学上确切地知道你最终得出的数字。但我可以猜测一下，而且我对我的预测非常有信心。我认为你最终会进入一个循环：1 → 4 → 2 → 1 。我说得对吗？

如果你愿意，可以再选一个新数字。我肯定又会猜对。事实上，我敢用我的名誉打赌，无论你选哪个数字，最终都会进入1→4→2的循环。

那么我怎么会这么自信呢？这都归功于一个著名的猜想：

定义函数 f 如下：

f(n) = n/2 ，当 n 为偶数时

f(n) = 3n + 1 ，当 n 为奇数时

现在，通过将 f 迭代应用于我们的起始数 f(n) 来形成一个数列。用符号表示，我们可以这样写：令 aᵢ 表示数列的第 i 个元素。然后，aᵢ₊₁ 迭代定义为 aᵢ₊₁ = f(aᵢ)，且 a₀ = n。

有时考虑数列的替代但等效的定义可能更有用：数列的第 i 个元素是将 f 应用于 n之后 i 次的结果，即 aᵢ = f(n)。

Collatz 猜想假设，对于任意整数 n≥1，此过程最终都会达到 1。也就是说，对于每个 n，都存在一个 i 使得 f(n) = 1。

各数字经过函数 f 最多 20 次迭代后达到 1 的图表

如果存在一个 i 使得 f(n) = 1，我会说“n 满足 Collatz 标准”。

你可能已经注意到，这个将 f 反复应用于 n 的过程正是我在文章开头要求你做的。如果 Collatz 猜想成立，并且我们确实总能得到 1，那么反复应用 f 就会让我们陷入 1 → 4 → 2 → 1 的循环，就像我在预测中所说的那样。那么我作弊了吗？算是吧。

尽管理解科拉茨（Collatz）猜想并不需要任何高深的数学知识，尽管它是由数学家洛萨·科拉茨（Lothar Collatz）在 1937 年提出的，距今已有近 100 年，但我们仍然不知道科拉茨猜想是否正确。因此，当我说我无法从数学上确定你最终会得到什么数字时，我并没有撒谎。然而，我们知道它对所有 n ≤2⁷⊃1; ≈ 2.36 ×10⊃2;⊃1;都成立。所以我实际上是在打赌你不会选一个大于 2 乘以 10的21次方（sextillion）的数字。如果是那样的话，我可以肯定你最终会陷入循环。

就我们游戏的目的而言，知道 2.36 乘以10的21次方以内的结果就足够了，因为如果有人选出比这个更大的数字，我会很震惊。但是，作为一名数学家，我发现这很不令人满意。我想确切地知道——科拉茨猜想对所有正整数 n 都成立吗？

计算需要多长时间……？

虽然我们还没有关于 Collatz 猜想是否成立的明确答案，但有一些强有力的证据表明它是正确的。正如我之前提到的，该猜想已被证明对 2⁷⊃1; 以下的所有值都成立。此值截至 2025年1月15日，由 David Barina 证明。

该表格展示了 David Barina 团队在证明 Collatz 猜想方面取得的进展。

读到这里时，我的第一个念头是想知道我的电脑要花多长时间才能完成。假设计算机遵循一个简单的算法——对每个 n，按升序测试，我们反复应用 f，只有当它达到 1 或达到循环时才停止。

粗略地讲，请注意，每次应用 f(n) 都需要一到两次计算。我的计算机的中央处理器 (CPU) 每秒大约可以执行 32 亿次计算。因此，即使每次应用 f 时每个整数都达到 1，我的计算机也需要大约 10⊃1;⊃3; 秒的时间来测试所有不超过 2⁷⊃1; 的整数。如果运行这些数字，我的计算机需要将近 25000 年才能完成所有测试。

当然，我的个人电脑绝对比不上实验室里的电脑。进行这种计算的研究人员也不太可能只利用一台电脑的计算能力。因此，你可能会认为，实际上用这种方法测试整数所需的时间远少于 2.5 万年。但别忘了，这是基于每个整数只需一次f运算就能达到 1 的假设。这根本不是事实！

只有一个整数只需使用一次 f 即可达到 1，即 2。事实上，除了 2（以及 1 本身）之外，所有整数都至少需要两步，而 n 达到 1 所需的步数始终至少为 log ₂ (n) （为了理解这一点，请注意 aᵢ = f(n) 要么是 aᵢ₋₁ 的 3 倍以上，要么是 aᵢ₋₁ 的一半。因此，其量级最多会缩小 2 倍。）。这意味着从 1 到 2⁷⊃1; 的整数中有一半至少需要 70 步，有些则需要更多步。

所以看来，即使拥有大量高性能计算机，这种简单的方法仍将耗费相当长的时间。这肯定比人类拥有计算机技术的时间还要长！因此，一定有某种方法可以加快我们的测试速度。

简化和筛选

为了加快算法速度，我们首先要意识到，我们不需要证明对于每个 n，都存在一个 i 使得 f(n) = 1，而实际上我们只需要证明对于每个 n>1，都存在一个 i 使得 f(n) < n。为什么这样就足够了？这意味着我们可以应用归纳论证：如果对于每个整数 1 ≤ k < n，且 f(n) < n，则f(n) 满足 Collatz 准则，且因此n也满足。

这已经加快了我们的算法速度，因为我们可以减少重复工作。尤其是当我们按升序测试 n 时，这意味着一旦达到一个已知适用 Collatz 准则的数字，我们就会停止。

另一种加速算法的方法是应用 Barina 所说的 3ᵏ 筛法。我会先向你展示 3⊃1; 筛法，然后再演示如何扩展它。首先观察

f⊃2;(2n + 1) = f(3(2n+1) + 1) = f(6n + 4) = 3n + 2

这里，f 的第一次应用是乘以 3 并加 1，因为 2n+1 是奇数。然后我们得到一个偶数，所以我们将其减半。因为我们是按照 n 的升序测试 n 是否满足 Collatz 准则，所以当我们测试 3n + 2 时，我们已经测试了 2n+1。因此，假设我们尚未找到 Collatz 猜想的反例，我们知道，当我们测试 3n+2 时，我们已经测试过了。

因此，我们不需要测试任何形式为 3n + 2 的数字——这些数字通常被称为 2 模 3 的数字。这将我们需要测试的数字数量减少了 ⅓。

这就是 3⊃1; 筛法。3⊃2; 筛法应用了类似的推理，但它考察的是 3⊃2; = 9 的模数。例如，反复应用 f 可得出

8n + 3 → (×3 + 1) → 24n + 10 →（÷2）→ 12n +5 → (×3 + 1)→ 36n + 16 → （÷2）→ 18n + 8 → （÷2）→ 9n + 4

因此，我们不需要测试任何形如 9n+4 的数字，即 4 模 9 的数字。此外，任何大于 2, 5 或 8 的数都是 2 模 3 的数，所以我们也不需要检查它们。这样就省去了我们需要检查的数字中的 4/9！

一张表格，显示哪些数字可以通过不同大小的筛子消除。

不幸的是，虽然这看起来是一个很有前景的方法，但应用 3ᵏ 筛法并不能消除 k>2 时的任何额外结果。因此，我们已经达到了这一改进的极限。

二进制？

通过将 n 转换为二进制，可以对算法进行最后的改进。

如果二进制表示以 k 个 1 结尾，我们可以应用 3n + 1，然后再应用 (n/2)（我们将其称为迭代 1）k 次。这将使我们原来的 n，其形式为 b2ᵏ -1 到 b3ᵏ -1，并有 k 组迭代 1。

如果二进制表示以 k 个零结尾，我们可以应用 n/2（我们将其称为迭代 2）k 次，每次本质上都是从二进制表示的末尾删除 k 个零。这将使我们原来的 n ，形式为 a2ᵏ 到 a，并有 k 组迭代 2。

例如，以 7 为例。7 的二进制表示为 111，2⊃3; - 1 也是如此。现在我们立即知道，经过 3 次迭代后，7 会变成 3⊃3; - 1 = 27 - 1 = 26。请注意，我们不知道从 7 到 26 需要经过哪些数字。我们只关心完成 3 次迭代后最终的结果。

现在我们到了 26。用二进制表示，26 = 11010。因此，在应用偶数步之后，它将变为 1101 = 13 = 7 ×2⊃1; -1。奇数步将变为 7 ×3⊃1; - 1 = 20。用二进制表示，20 = 10100，依此类推。

换句话说，我们已经证明了

7 → … → 26 → … → 13 → … → 20 →...

记住，我们不关心数列中间有哪些数字。通过允许我们直接跳到 k 次迭代的最终结果，我们可以节省大量的计算时间。事实上，对于奇数 n，我们在每次应用算法时平均计算 4 次迭代。

下一步是什么？

上述方法已被用来加速测试整数是否满足 Collatz 准则，并且我相信它们还会继续被用来证明该猜想对越来越大的 n 成立。那么，它何时会停止呢？

显然，如果我们找到一个反例，就立即推翻了科拉茨猜想，我们的探索也就此终止。另一方面，随着我们发现每一个满足科拉茨准则的新数字，我们就能越来越确信科拉茨猜想是正确的。但不幸的是，这永远不足以确定。数学家们经历了惨痛的教训才明白这一点。

长期以来，人们一直认为波利亚猜想（Pólya conjecture）是正确的。该猜想声称，对于任意的 N，至少有一半小于 N 的自然数，其素因数个数为奇数。从 1919 年波利亚提出该猜想开始，直到 1958 年 C. Brian Haselgrove 发现一个大约为 1.845 ×10⊃3;⁶⊃1; 的反例之前，人们都相信该猜想是正确的。

所以，就目前而言，Collatz 猜想仍然只是一个猜想。也许最终证明它的人会是你。