【原】小樂(lè)數(shù)學(xué)科普：一個(gè)名叫Collatz猜想（科拉茨猜想、考拉茲猜想，也稱3n+1、冰雹猜想）的未解難題——譯自海德堡桂冠論壇HLF

zzllrr小樂(lè) 2025-08-28 發(fā)布于江蘇

展開全文

★加星zzllrr小樂(lè)公眾號(hào)數(shù)學(xué)科普不迷路！

Collat??z 猜想指出，如果你選擇一個(gè)正整數(shù)，如果它是偶數(shù)，就將其除以2，如果它是奇數(shù)，就將其乘以3并加上1，最終都會(huì)得到1。

作者：Sophie Maclean（倫敦國(guó)王學(xué)院解析數(shù)論在讀博士生）2025-8-27

譯者：zzllrr小樂(lè)（數(shù)學(xué)科普公眾號(hào)）2025-8-28

我要你選一個(gè)正整數(shù)。任意一個(gè)都可以——你可以自由選擇。如果你選的是奇數(shù)，就把它乘以 3，再加 1。如果是偶數(shù)，就把它減半。取得結(jié)果并重復(fù)這個(gè)過(guò)程。實(shí)際上，我想讓你一直重復(fù)，直到你陷入循環(huán)。

例如，如果你的數(shù)字是 7，你首先要乘以 3，再加 1，得到 22。現(xiàn)在你得到的是一個(gè)偶數(shù)，所以你需要將其減半得到 11。11 是奇數(shù)，而 3 × 11 + 1 = 34。然后這個(gè)模式會(huì)繼續(xù)下去……

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

事實(shí)證明，用箭頭表示是一種非常有用的符號(hào)。我們可以將 11 的路徑表示為 11 → 34 → 17 → 52 → 26 → 13 →……

現(xiàn)在輪到你了。選一個(gè)你自己的數(shù)字，然后按照算法走，直到你發(fā)現(xiàn)自己陷入了循環(huán)。完成了嗎？

好的。

首先我要說(shuō)的是，我無(wú)法從數(shù)學(xué)上確切地知道你最終得出的數(shù)字。但我可以猜測(cè)一下，而且我對(duì)我的預(yù)測(cè)非常有信心。我認(rèn)為你最終會(huì)進(jìn)入一個(gè)循環(huán)：1 → 4 → 2 → 1 。我說(shuō)得對(duì)嗎？

如果你愿意，可以再選一個(gè)新數(shù)字。我肯定又會(huì)猜對(duì)。事實(shí)上，我敢用我的名譽(yù)打賭，無(wú)論你選哪個(gè)數(shù)字，最終都會(huì)進(jìn)入1→4→2的循環(huán)。

那么我怎么會(huì)這么自信呢？這都?xì)w功于一個(gè)著名的猜想：

定義函數(shù) f 如下：

f(n) = n/2 ，當(dāng) n 為偶數(shù)時(shí)
f(n) = 3n + 1 ，當(dāng) n 為奇數(shù)時(shí)

現(xiàn)在，通過(guò)將 f 迭代應(yīng)用于我們的起始數(shù) f(n) 來(lái)形成一個(gè)數(shù)列。用符號(hào)表示，我們可以這樣寫：令 a? 表示數(shù)列的第 i 個(gè)元素。然后，a??? 迭代定義為 a??? = f(a?)，且 a? = n。

有時(shí)考慮數(shù)列的替代但等效的定義可能更有用：數(shù)列的第 i 個(gè)元素是將 f 應(yīng)用于 n之后 i 次的結(jié)果，即 a? = f?(n)。

Collat??z 猜想假設(shè)，對(duì)于任意整數(shù) n≥1，此過(guò)程最終都會(huì)達(dá)到 1。也就是說(shuō)，對(duì)于每個(gè) n，都存在一個(gè) i 使得 f?(n) = 1。

各數(shù)字經(jīng)過(guò)函數(shù) f 最多 20 次迭代后達(dá)到 1 的圖表

如果存在一個(gè) i 使得 f?(n) = 1，我會(huì)說(shuō)“n 滿足 Collat??z 標(biāo)準(zhǔn)”。

你可能已經(jīng)注意到，這個(gè)將 f 反復(fù)應(yīng)用于 n 的過(guò)程正是我在文章開頭要求你做的。如果 Collat??z 猜想成立，并且我們確實(shí)總能得到 1，那么反復(fù)應(yīng)用 f 就會(huì)讓我們陷入 1 → 4 → 2 → 1 的循環(huán)，就像我在預(yù)測(cè)中所說(shuō)的那樣。那么我作弊了嗎？算是吧。

盡管理解科拉茨（Collatz）猜想并不需要任何高深的數(shù)學(xué)知識(shí)，盡管它是由數(shù)學(xué)家洛薩·科拉茨（Lothar Collatz）在 1937 年提出的，距今已有近 100 年，但我們?nèi)匀徊恢揽评牟孪胧欠裾_。因此，當(dāng)我說(shuō)我無(wú)法從數(shù)學(xué)上確定你最終會(huì)得到什么數(shù)字時(shí)，我并沒有撒謊。然而，我們知道它對(duì)所有 n ≤2?1 ≈ 2.36 ×1021都成立。所以我實(shí)際上是在打賭你不會(huì)選一個(gè)大于 2 乘以 10的21次方（sextillion）的數(shù)字。如果是那樣的話，我可以肯定你最終會(huì)陷入循環(huán)。

就我們游戲的目的而言，知道 2.36 乘以10的21次方以內(nèi)的結(jié)果就足夠了，因?yàn)槿绻腥诉x出比這個(gè)更大的數(shù)字，我會(huì)很震驚。但是，作為一名數(shù)學(xué)家，我發(fā)現(xiàn)這很不令人滿意。我想確切地知道——科拉茨猜想對(duì)所有正整數(shù) n 都成立嗎？

計(jì)算需要多長(zhǎng)時(shí)間……？

雖然我們還沒有關(guān)于 Collat??z 猜想是否成立的明確答案，但有一些強(qiáng)有力的證據(jù)表明它是正確的。正如我之前提到的，該猜想已被證明對(duì) 2?1 以下的所有值都成立。此值截至 2025年1月15日，由 David Barina 證明。

該表格展示了 David Barina 團(tuán)隊(duì)在證明 Collat??z 猜想方面取得的進(jìn)展。

讀到這里時(shí)，我的第一個(gè)念頭是想知道我的電腦要花多長(zhǎng)時(shí)間才能完成。假設(shè)計(jì)算機(jī)遵循一個(gè)簡(jiǎn)單的算法——對(duì)每個(gè) n，按升序測(cè)試，我們反復(fù)應(yīng)用 f，只有當(dāng)它達(dá)到 1 或達(dá)到循環(huán)時(shí)才停止。

粗略地講，請(qǐng)注意，每次應(yīng)用 f(n) 都需要一到兩次計(jì)算。我的計(jì)算機(jī)的中央處理器 (CPU) 每秒大約可以執(zhí)行 32 億次計(jì)算。因此，即使每次應(yīng)用 f 時(shí)每個(gè)整數(shù)都達(dá)到 1，我的計(jì)算機(jī)也需要大約 1013 秒的時(shí)間來(lái)測(cè)試所有不超過(guò) 2?1 的整數(shù)。如果運(yùn)行這些數(shù)字，我的計(jì)算機(jī)需要將近 25000 年才能完成所有測(cè)試。

當(dāng)然，我的個(gè)人電腦絕對(duì)比不上實(shí)驗(yàn)室里的電腦。進(jìn)行這種計(jì)算的研究人員也不太可能只利用一臺(tái)電腦的計(jì)算能力。因此，你可能會(huì)認(rèn)為，實(shí)際上用這種方法測(cè)試整數(shù)所需的時(shí)間遠(yuǎn)少于 2.5 萬(wàn)年。但別忘了，這是基于每個(gè)整數(shù)只需一次f運(yùn)算就能達(dá)到 1 的假設(shè)。這根本不是事實(shí)！

只有一個(gè)整數(shù)只需使用一次 f 即可達(dá)到 1，即 2。事實(shí)上，除了 2（以及 1 本身）之外，所有整數(shù)都至少需要兩步，而 n 達(dá)到 1 所需的步數(shù)始終至少為 log ? (n) （為了理解這一點(diǎn)，請(qǐng)注意 a? = f?(n) 要么是 a??? 的 3 倍以上，要么是 a??? 的一半。因此，其量級(jí)最多會(huì)縮小 2 倍。）。這意味著從 1 到 2?1 的整數(shù)中有一半至少需要 70 步，有些則需要更多步。

所以看來(lái)，即使擁有大量高性能計(jì)算機(jī)，這種簡(jiǎn)單的方法仍將耗費(fèi)相當(dāng)長(zhǎng)的時(shí)間。這肯定比人類擁有計(jì)算機(jī)技術(shù)的時(shí)間還要長(zhǎng)！因此，一定有某種方法可以加快我們的測(cè)試速度。

簡(jiǎn)化和篩選

為了加快算法速度，我們首先要意識(shí)到，我們不需要證明對(duì)于每個(gè) n，都存在一個(gè) i 使得 f?(n) = 1，而實(shí)際上我們只需要證明對(duì)于每個(gè) n>1，都存在一個(gè) i 使得 f?(n) < n。為什么這樣就足夠了？這意味著我們可以應(yīng)用歸納論證：如果對(duì)于每個(gè)整數(shù) 1 ≤ k < n，且 f?(n) < n，則f?(n) 滿足 Collat??z 準(zhǔn)則，且因此n也滿足。

這已經(jīng)加快了我們的算法速度，因?yàn)槲覀兛梢詼p少重復(fù)工作。尤其是當(dāng)我們按升序測(cè)試 n 時(shí)，這意味著一旦達(dá)到一個(gè)已知適用 Collat??z 準(zhǔn)則的數(shù)字，我們就會(huì)停止。

另一種加速算法的方法是應(yīng)用 Barina 所說(shuō)的 3? 篩法。我會(huì)先向你展示 31 篩法，然后再演示如何擴(kuò)展它。首先觀察

f2(2n + 1) = f(3(2n+1) + 1) = f(6n + 4) = 3n + 2

這里，f 的第一次應(yīng)用是乘以 3 并加 1，因?yàn)?2n+1 是奇數(shù)。然后我們得到一個(gè)偶數(shù)，所以我們將其減半。因?yàn)槲覀兪前凑?n 的升序測(cè)試 n 是否滿足 Collat??z 準(zhǔn)則，所以當(dāng)我們測(cè)試 3n + 2 時(shí)，我們已經(jīng)測(cè)試了 2n+1。因此，假設(shè)我們尚未找到 Collat??z 猜想的反例，我們知道，當(dāng)我們測(cè)試 3n+2 時(shí)，我們已經(jīng)測(cè)試過(guò)了。

因此，我們不需要測(cè)試任何形式為 3n + 2 的數(shù)字——這些數(shù)字通常被稱為 2 模 3 的數(shù)字。這將我們需要測(cè)試的數(shù)字?jǐn)?shù)量減少了 ?。

這就是 31 篩法。32 篩法應(yīng)用了類似的推理，但它考察的是 32 = 9 的模數(shù)。例如，反復(fù)應(yīng)用 f 可得出

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

因此，我們不需要測(cè)試任何形如 9n+4 的數(shù)字，即 4 模 9 的數(shù)字。此外，任何大于 2, 5 或 8 的數(shù)都是 2 模 3 的數(shù)，所以我們也不需要檢查它們。這樣就省去了我們需要檢查的數(shù)字中的 4/9！

一張表格，顯示哪些數(shù)字可以通過(guò)不同大小的篩子消除。

不幸的是，雖然這看起來(lái)是一個(gè)很有前景的方法，但應(yīng)用 3? 篩法并不能消除 k>2 時(shí)的任何額外結(jié)果。因此，我們已經(jīng)達(dá)到了這一改進(jìn)的極限。

二進(jìn)制？

通過(guò)將 n 轉(zhuǎn)換為二進(jìn)制，可以對(duì)算法進(jìn)行最后的改進(jìn)。

如果二進(jìn)制表示以 k 個(gè) 1 結(jié)尾，我們可以應(yīng)用 3n + 1，然后再應(yīng)用 (n/2)（我們將其稱為迭代 1）k 次。這將使我們?cè)瓉?lái)的 n，其形式為 b2? -1 到 b3? -1，并有 k 組迭代 1。

如果二進(jìn)制表示以 k 個(gè)零結(jié)尾，我們可以應(yīng)用 n/2（我們將其稱為迭代 2）k 次，每次本質(zhì)上都是從二進(jìn)制表示的末尾刪除 k 個(gè)零。這將使我們?cè)瓉?lái)的 n ，形式為 a2? 到 a，并有 k 組迭代 2。

例如，以 7 為例。7 的二進(jìn)制表示為 111，23 - 1 也是如此。現(xiàn)在我們立即知道，經(jīng)過(guò) 3 次迭代后，7 會(huì)變成 33 - 1 = 27 - 1 = 26。請(qǐng)注意，我們不知道從 7 到 26 需要經(jīng)過(guò)哪些數(shù)字。我們只關(guān)心完成 3 次迭代后最終的結(jié)果。

現(xiàn)在我們到了 26。用二進(jìn)制表示，26 = 11010。因此，在應(yīng)用偶數(shù)步之后，它將變?yōu)?1101 = 13 = 7 ×21 -1。奇數(shù)步將變?yōu)?7 ×31 - 1 = 20。用二進(jìn)制表示，20 = 10100，依此類推。

換句話說(shuō)，我們已經(jīng)證明了

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

記住，我們不關(guān)心數(shù)列中間有哪些數(shù)字。通過(guò)允許我們直接跳到 k 次迭代的最終結(jié)果，我們可以節(jié)省大量的計(jì)算時(shí)間。事實(shí)上，對(duì)于奇數(shù) n，我們?cè)诿看螒?yīng)用算法時(shí)平均計(jì)算 4 次迭代。

下一步是什么？

上述方法已被用來(lái)加速測(cè)試整數(shù)是否滿足 Collat??z 準(zhǔn)則，并且我相信它們還會(huì)繼續(xù)被用來(lái)證明該猜想對(duì)越來(lái)越大的 n 成立。那么，它何時(shí)會(huì)停止呢？

顯然，如果我們找到一個(gè)反例，就立即推翻了科拉茨猜想，我們的探索也就此終止。另一方面，隨著我們發(fā)現(xiàn)每一個(gè)滿足科拉茨準(zhǔn)則的新數(shù)字，我們就能越來(lái)越確信科拉茨猜想是正確的。但不幸的是，這永遠(yuǎn)不足以確定。數(shù)學(xué)家們經(jīng)歷了慘痛的教訓(xùn)才明白這一點(diǎn)。

長(zhǎng)期以來(lái)，人們一直認(rèn)為波利亞猜想（Pólya conjecture）是正確的。該猜想聲稱，對(duì)于任意的 N，至少有一半小于 N 的自然數(shù)，其素因數(shù)個(gè)數(shù)為奇數(shù)。從 1919 年波利亞提出該猜想開始，直到 1958 年 C. Brian Haselgrove 發(fā)現(xiàn)一個(gè)大約為 1.845 ×103?1 的反例之前，人們都相信該猜想是正確的。

所以，就目前而言，Collat??z 猜想仍然只是一個(gè)猜想。也許最終證明它的人會(huì)是你。

“Collat??z 猜想”（xkcd漫畫幽默說(shuō)法版本）指出，如果你選擇一個(gè)數(shù)字，如果它是偶數(shù)，就將其除以2，如果它是奇數(shù)，就將其乘以3并加上1，并且你重復(fù)此過(guò)程足夠長(zhǎng)的時(shí)間，最終你的朋友將不再打電話來(lái)見你，而是想出去玩。

圖源： https:///710/