考拉茲猜想

考拉茲猜想（英語：Collatz conjecture），又稱為奇偶歸一猜想、3n+1猜想、冰雹猜想、角谷猜想、哈塞猜想、烏拉姆猜想或敘拉古猜想，^[1]是指對於每一個正整數，如果它是奇數，則對它乘3再加1，如果它是偶數，則對它除以2，如此循環，最終都能夠得到1。

${\displaystyle f(n)={\begin{cases}n/2&{\mbox{if }}n\equiv 0\\3n+1&{\mbox{if }}n\equiv 1\end{cases}}{\pmod {2}}.}$

埃爾德什·帕爾在談到考拉茲猜想時說：「數學還沒準備好應對這樣的問題。」^[2]傑佛瑞·拉加里亞斯（英語：Jeffrey Lagarias）指出，考拉茲猜想「是個異常困難的問題，完全超出了當今數學的範圍」。^[3]

問題表述

1到9999的數字及其相應的停止時間

1到10⁸的總停止時間直方圖，x軸為總停止時間，y軸為頻率。

1到10⁹的總停止時間柱狀圖直方圖，x軸為總停止時間，y軸為頻率。

2到10⁷的迭代時間

總停止時間：最高250、1000、4000、20000、100000、500000的數字

對任意正整數進行以下運算；

• 若為偶數，則除以2；
• 若為奇數，則將其×3再加1。

這可以定義為模算術函數f： $${\displaystyle f(n)={\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$

現重複執行該運算，形成一個序列，從任意正整數開始，把每步的結果作為下一步的輸入。可記作： $${\displaystyle a_{i}={\begin{cases}n&{\text{for }}i=0,\\f(a_{i-1})&{\text{for }}i>0\end{cases}}}$$ （即：a_i是遞歸i次應用於n的f值；a_i = f ⁱ(n)）。

考拉茲猜想是：所有正整數最終都會到達1，即存在i使得a_i = f ⁱ(n)= 1。

若猜想為假，表示存在某個初值產生一個不含1的循環數列，或朝無窮大發散的數列，目前尚未發現這樣的數列。

最小的使a_i < a₀ 的i稱為n的停止時間，相似地，使a_k = 1的最小的k稱為n的總停止時間。^[4]若索引i或k的其中一個不存在，就稱停止時間或總停止時間分別不存在。

考拉茲猜想認為，所有n的總停止時間都是有限的，即所有n ≥ 2都有有限的停止時間。

只要n是奇數，3n + 1就是偶數，所以可以使用考拉茲函數的「快捷」形式： $${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$ 這個定義可在過程整體動態不變的前提下，獲得較小的停止時間和總停止時間值。

經驗數據

取一個正整數：

• 如${\displaystyle n}$ = 6，根據上述數式，得出序列6, 3, 10, 5, 16, 8, 4, 2, 1。（步驟中最高的數是16，共有8個步驟）
• 如${\displaystyle n}$ = 11，根據上述數式，得出序列11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。（步驟中最高的數是52，共有14個步驟）
• 如${\displaystyle n}$ = 27，根據上述數式，得出序列 {27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1}（步驟中最高的數是9232，共有111個步驟）（OEIS數列A008884）

奇偶歸一猜想稱，任何正整數，經過上述計算步驟後，最終都會得到1。

${\displaystyle n}$=27時的序列分佈（橫軸－步數；縱軸－運算結果）

數目少於1萬的，有着最高步驟數的是6171，共有261個步驟；數目少於10萬的，有着最高步驟數的是77031，共有350個步驟；數目少於100萬的，有着最高步驟數的是837799，共有524個步驟；數目少於1億的，有着最高步驟數的是63728127，共有949個步驟；數目少於10億的，有着最高步驟數的是670617279，共有986個步驟。

總停止時間長於任何較小起始值的數字構成如下序列：

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ... （OEIS數列A006877）

最大軌跡點大於任何較小起始值的起始值構成如下序列

1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ... （OEIS數列A006884）

n達到1的步數為

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... （OEIS數列A006577）

總停止時間最長，且

小於10的是9，經歷19步；

小於100的是97，經歷118步；

小於1000的是871，經歷178步；

小於10⁴的是6171，經歷261步；

小於10⁵的是7004770310000000000♠77031，經歷350步；

小於10⁶的是7005837799000000000♠837799，經歷524步；

小於10⁷的是7006840051100000000♠8400511，經歷685步；

小於10⁸的是7007637281270000000♠63728127，經歷949步；

小於10⁹的是7008670617279000000♠670617279，經歷986步；

小於10¹⁰的是7009978065763000000♠9780657630，經歷1132步；^[5]

小於10¹¹的是7010751281382470000♠75128138247，經歷1228步；

小於10¹²的是7011989345275647000♠989345275647，經歷1348步；……^[6] （OEIS數列A284668）

這些數字也是具有指定步數的最低數字，但不一定是唯一的，例如經歷1132步的有7009978065763100000♠9780657631，還有7009978065763000000♠9780657630。

與位數（以2為基）相關的總停止時間最小的起始值是2的冪，因為2ⁿ經歷n次減半才達到1，且永遠不會增加。

可視化

• 
  前1000個數的軌跡的有向圖
• 
  x軸表示初始數，y軸表示到1過程中到達的最大值。此圖顯示了壓縮的y軸：有些x值產生的軌跡最大值可達7007270000000000000♠2.7×10⁷（x = 9663）
• 
  與左圖相同，但採用對數坐標，顯示了所有y值。圖中間的第一條粗線對應27處的尖端，在9232到達最大值
• 
  小於20步的所有數集合
• 
  前1億個數到達1的迭代次數

支持論據

雖然猜想尚未得到證實，但大多數數學家都認為它是真的，因為實驗證據和啟發式論證都支持這一猜想。

實驗證據

截至2020年，已經用計算機驗證了2⁶⁸ ≈ 7020295000000000000♠2.95×10²⁰之前的所有初始值，最終都以周期為3的循環(4; 2; 1)作結。^[7]

顯然，這不能證明猜想對所有初始值都正確，因為非常大的正整數可能會出現反例，例如希爾伯特－波利亞猜想的反例。不過，這種驗證可能會產生其他影響，例如我們可以推導出關於非平凡周期和結構形式的額外約束。^{[8][9][10][需要解釋]}

概率啟發式

若只考慮考拉茲過程產生序列中的奇數，那麼每個奇數平均都是前一個的3/4。^[11]（更準確地說，結果的幾何均值是3/4。）這就產生了啟發式論證：每個考拉茲序列從長期來看都傾向於減小，雖然這不能證明不存在其他的周期。這個論證不是證明，因為它假定考拉茲序列是由不相關的概率事件組合而成的。（確實嚴格證明了考拉茲過程的2進數推廣在幾乎所有初始值的每個乘法步驟都對應兩個除法步驟）

停止時間

正如Riho Terras證明，幾乎每個正整數都有有限的停止時間。^[12]換句話說，幾乎每個考拉茲序列都會到達嚴格低於其初值的點。該證明基於奇偶向量的分佈，並利用了中心極限定理。

2019年，陶哲軒利用概率密度函數改進了這一結果，證明幾乎所有（對數密度意義上的）考拉茲軌道都在起點的任意發散函數之下。《量子雜誌》在回應這項工作時寫道，陶哲軒「獲得了幾十年來關於考拉茲猜想的最重要成果之一」。^[13][14]

下界

Krasikov & Lagarias在一份計算機輔助證明中證明，對所有足夠大的x，區間[1,x]中最終達到1的整數個數至少等於x^0.84。^[15]

循環

在這一節中，考慮考拉茲函數的快捷形式 $${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$ 循環是由不同正整數組成的序列(a₀, a₁, ..., a_q)，其中f(a₀) = a₁, f(a₁) = a₂, ..., f(a_q) = a₀。

唯一已知的循環是周期為2的(1,2)，稱作平凡循環。

周期長度

非平凡周期的長度至少為7011186265759595000♠186265759595。若能證明對所有小於${\displaystyle 3\times 2^{69}}$的正整數，考拉茲序列都收斂到1，則這個下界就會提高到7011355504839929000♠355504839929。^[16][9]實際上，Eliahou (1993)證明了任何非平凡循環的周期p的形式為 $${\displaystyle p=301994a+17087915b+85137581c}$$ 其中a、b、c為非負整數，b ≥ 1，ac = 0。這個結果是基於ln 3/ln 2的連分數展開。^[9]

k循環

k循環是可分為k段連續子列的循環，每個子列由奇數的遞增序列和偶數的遞減序列組成。^[10]例如，若循環由1個奇數的遞增序列和偶數的遞減序列組成，則稱為1循環。

Steiner (1977)證明，除平凡循環(1; 2)外不存在其他1循環。^[17]Simons (2005)用Steiner的方法證明沒有2循環。^[18] Simons & de Weger (2005)將這一證明推廣到68循環，即k = 68以下不存在k循環。^[10]Hercher進一步推廣了這一方法，證明不存在k≤91的k循環。^[16]隨着計算機窮舉搜索的繼續，可能會排除更大的k值。

猜想的其他表述

反向

自下而上生成的考拉茲圖的前21層。包含所有軌道長度小於等於21的數字

還有另一種方法可證明這猜想：採用自下而上的方法構造所謂考拉茲圖，由逆關係定義： $${\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1,2,3,5\\[4px]\left\{2n,{\frac {n-1}{3}}\right\}&{\text{if }}n\equiv 4\end{cases}}{\pmod {6}}.}$$

因此，與其證明所有正整數都指向1，我們可以嘗試證明1指向所有正整數。對任意整數n，n ≡ 1 (mod 2)若且唯若3n + 1 ≡ 4 (mod 6)。等價地，n − 1/3 ≡ 1 (mod 2)若且唯若n ≡ 4 (mod 6)。根據猜想，除了1-2-3循環之外，這個逆關係構成一棵樹。

函數f的關係式3n + 1可用「快捷」關係式3n + 1/2代替，則考拉茲圖由逆關係定義： $${\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1\\[4px]\left\{2n,{\frac {2n-1}{3}}\right\}&{\text{if }}n\equiv 2\end{cases}}{\pmod {3}}.}$$

對任意整數n，n ≡ 1 (mod 2)若且唯若3n + 1/2 ≡ 2 (mod 3)。等價地，2n − 1/3 ≡ 1 (mod 2)若且唯若n ≡ 2 (mod 3)。根據猜想，除了1-2循環之外，這個逆關係構成一棵樹。

或者，把3n + 1換成n′/H(n′)，其中n′ = 3n + 1、H(n′)是整除n′的最大的2的冪，得到的函數f將從奇數映射到奇數。現假設對某個奇數n，進行k次運算會得到數字1（即f^k(n) = 1）。則數字n在二進制中可寫為字符串w_k w_k−1 ... w₁，其中每個w_h都是從1/3^h的表示中提取的有限連續字符串。^[19]因此，n的表示包含了除1/3^h的重複尾數，每個重複尾數可以選擇旋轉，再複製到有限位數。只有二進制會出現這種情況。^[20]根據猜想，每個以「1」結尾的二進制字符串s都可用這種形式表示（可以添加或刪除s的前導0）。

作為以二進制計算的抽象機

考拉茲函數的重複應用可用處理比特串的抽象機表示。它會對任何奇數執行以下3步，直到只剩一個1:

1. 在二進制數的（右）端加1（得到2n + 1）；
2. 用二進制加法將其加到原數上（2n + 1 + n = 3n + 1）；
3. 去掉所有尾數0（反覆除以2直到結果為奇數）。

示例

起始值為7，以二進制寫作111。得到的考拉茲序列為：

         111
        1111
       10110
      10111
     100010
    100011
    110100
   11011
  101000
 1011
10000

作為奇偶序列

本節中，考慮略微修改的考拉茲函數 $${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1\end{cases}}{\pmod {2}}.}$$

這樣做是因為n為奇數時，3n + 1總是偶數。

若P(...)表示某數的奇偶性，例如P(2n) = 0、P(2n + 1) = 1，則可定義一個數n的考拉茲奇偶序列p_i = P(a_i)，其中a₀ = n；a_i+1 = f(a_i)。

執行3n + 1/2還是n/2的哪種運算取決於奇偶性，序列與運算序列相同。

利用f(n)的這種形式，可證明兩個數m、n的奇偶性序列在前k項上一致，若且唯若m、n是等價的模2^k。這意味着每個數都能通過奇偶性序列唯一識別，此外若存在多個考拉茲循環，則它們對應的奇偶性循環也一定是不同的。^[4][12]

對數n = 2^ka + b應用k次f函數，得到3^ca + d，其中d是對b應用k次f函數的結果，c是在序列中增加的次數。例如，對於2⁵a + 1，1依次上升到2、1、2、1，最後上升到2時有3次上升，因此結果是3³a + 2；對於2²a + 1只有一次上升：1、2、1，所以結果是3a + 1。b是2^k − 1時，會有k次上升，結果是3^ka + 3^k − 1。3的冪乘a與a無關，只取決於b的行為，這使我們可以預測，某些形式的數在迭代一定次數後總會到達更小的數字，例如4a + 1在應用兩次f後會變成3a + 1，16a + 3應用4次會變成9a + 2。不過，這些小數是否繼續下降到1則取決於a的值。

作為標記系統

對於形式為

${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1.\end{cases}}{\pmod {2}}}$

的考拉茲函數，考拉茲序列可通過2標記系統計算，生成規則為

a → bc, b → a, c → aaa.

系統中，正整數n由包含n份a的字符串表示，標籤操作的迭代在熱河長度小於2的詞上停止（改編自De Mol）。

考拉茲猜想等價地指出，以任意有限的a字符串作為初值，標記系統最終會停止。

推廣

在所有整數上迭代

考拉茲猜想的擴展是包含所有整數，而不僅僅是正整數。撇開無法從外部進入的0→0循環，已知循環共有4個，所有非零整數似乎都會在f的迭代下陷入其中：

奇數值用大粗體表示，每個循環以其絕對值最小的成員（總是奇數）為先列出。

循環	奇數值循環長度	全循環長度
1 → 4 → 2 → 1 ...	1	3
−1 → −2 → −1 ...	1	2
−5 → −14 → −7 → −20 → −10 → −5 ...	2	5
−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 ...	7	18

推廣的考拉茲猜想：在f的迭代下，所有整數最終都會落入上述4個循環或0→0循環中的一個。

奇分母有理數的迭代

考拉茲映射可擴展到奇分母的有理數。根據分子的奇偶，可將有理數分奇偶，然後映射數式與域為整數時完全相同：偶有理數除以2，奇有理數乘以3再加1。一個密切相關的事實是，考拉茲猜想可推廣到2進整數，其中包含作為子環的奇分母有理數環。

運用「快捷」函數時，已知任何周期的奇偶性序列都恰好由一個有理數生成。^[21]相反，有人猜想，每個奇分母有理數都有最終循環的奇偶性序列（周期性猜想^[4])）。

若奇偶循環長為n，且在k₀ < ⋯ < k_m−1處包含了m次奇數，那麼立即周期性地產生奇偶循環的唯一有理數：

${\displaystyle {\frac {3^{m-1}2^{k_{0}}+\cdots +3^{0}2^{k_{m-1}}}{2^{n}-3^{m}}}.}$

1

例如，奇偶循環(1 0 1 1 0 0 1)長度為7，4個奇數項分別位於0、2、3、6處。它由分數 $${\displaystyle {\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {151}{47}}}$$ 因為後者可產生有理循環 $${\displaystyle {\frac {151}{47}}\rightarrow {\frac {250}{47}}\rightarrow {\frac {125}{47}}\rightarrow {\frac {211}{47}}\rightarrow {\frac {340}{47}}\rightarrow {\frac {170}{47}}\rightarrow {\frac {85}{47}}\rightarrow {\frac {151}{47}}.}$$

(1 0 1 1 0 0 1)的任何循環排列都與上述分數之一相關。例如，循環(0 1 1 0 0 1 1)可由下面的分數產生 $${\displaystyle {\frac {3^{3}2^{1}+3^{2}2^{2}+3^{1}2^{5}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {250}{47}}.}$$

為實現一一對應，奇偶循環應是不可還原的，即無法分割成相同的子循環。例如，奇偶循環(1 1 0 0 1 1 0 0)及其子循環(1 1 0 0)在化為最小項時與相同的分數5/7相關。

這時，假設考拉茲猜想成立，就意味着(1 0)、(0 1)是唯一由正整數（1、2）產生的奇偶性循環。

若有理數的奇分母d不是3的倍數，則所有迭代數都將有相同的分母，通過應用考拉茲函數的3n + d推廣^[22]，可得考拉茲函數 $${\displaystyle T_{d}(x)={\begin{cases}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}},\\[4px]{\frac {3x+d}{2}}&{\text{if }}x\equiv 1{\pmod {2}}.\end{cases}}}$$

2進數推廣

函數 $${\displaystyle T(x)={\begin{cases}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}}\\[4px]{\frac {3x+1}{2}}&{\text{if }}x\equiv 1{\pmod {2}}\end{cases}}}$$ 在2進整環${\displaystyle \mathbb {Z} _{2}}$上有精確定義，是連續的，且關於2進度量是保測的。另外，已知其動態是遍歷的。^[4]

定義作用於${\displaystyle \mathbb {Z} _{2}}$的奇偶向量函數Q： $${\displaystyle Q(x)=\sum _{k=0}^{\infty }\left(T^{k}(x)\mod 2\right)2^{k}.}$$

函數Q是2進等距同構。^[23]因此，每個無限奇偶性序列都恰好出現一惡搞2進整數，所以幾乎所有軌跡在${\displaystyle \mathbb {Z} _{2}}$中都是非循環的。

考拉茲猜想的等價表述是 $${\displaystyle Q\left(\mathbb {Z} ^{+}\right)\subset {\tfrac {1}{3}}\mathbb {Z} .}$$

在實數、複數上的迭代

10 → 5 → 8 → 4 → 2 → 1 → ..迭代軌跡的蜘蛛圖。運用了推廣到實數的考拉茲映射。

${\displaystyle x}$為整偶數時${\displaystyle x/2}$、為整奇數時${\displaystyle 3x+1}$或${\displaystyle (3x+1)/2}$（「快捷」版本）的函數，可將考拉茲映射推廣到實數，這就是所謂的插值函數。一個簡單方法是選取兩個函數${\displaystyle g_{1}}$、${\displaystyle g_{2}}$，其中

${\displaystyle g_{1}(n)={\begin{cases}1,&n{\text{ is even,}}\\0,&n{\text{ is odd,}}\end{cases}}}$

${\displaystyle g_{2}(n)={\begin{cases}0,&n{\text{ is even,}}\\1,&n{\text{ is odd,}}\end{cases}}}$

並將它們作為我們所需值的開關：

${\displaystyle f(x)\triangleq {\frac {x}{2}}\cdot g_{1}(x)\,+\,{\frac {3x+1}{2}}\cdot g_{2}(x)}$.

其中一個選擇是${\displaystyle g_{1}(x)\triangleq \cos ^{2}\left({\tfrac {\pi }{2}}x\right)}$、${\displaystyle g_{2}(x)\triangleq \sin ^{2}\left({\tfrac {\pi }{2}}x\right)}$。這映射的迭代產生了動力系統，Marc Chamberland對其進行了進一步研究。^[24]他證明這個猜想對於正實數不成立，因為存在無窮多個不動點與無窮多單調發散到無窮的軌道。函數${\displaystyle f}$有2個周期為${\displaystyle 2}$的吸引子循環：${\displaystyle (1;\,2)}$、${\displaystyle (1.1925...;\,2.1386...)}$。此外，我們猜想無界軌道集的勒貝格測度為${\displaystyle 0}$。

Letherman、Schleicher和Wood將研究推廣到複平面，^[25]用張伯倫函數求解復正餘弦，並添加了額外項${\displaystyle {\tfrac {1}{\pi }}\left({\tfrac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)\,+}$ ${\displaystyle h(z)\sin ^{2}(\pi z)}$，其中${\displaystyle h(z)}$是任意整函數。由於該式對整實數求值為零，所以推廣函數

${\displaystyle {\begin{aligned}f(z)\triangleq \;&{\frac {z}{2}}\cos ^{2}\left({\frac {\pi }{2}}z\right)+{\frac {3z+1}{2}}\sin ^{2}\left({\frac {\pi }{2}}z\right)\,+\\&{\frac {1}{\pi }}\left({\frac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)+h(z)\sin ^{2}(\pi z)\end{aligned}}}$

是考拉茲映射到複平面的插值。添加額外項將所有整數都變為${\displaystyle f}$的臨界點，於是可證明沒有一個整數位於Baker域中，意味着任何整數或者是周期性的，或者屬於遊蕩域。他們猜想後者不成立，也就可以導出，所有整數軌都是有限的。

以原點為中心的考拉茲分形，實部為-5到5。

大部分點的軌道發散，根據發散速度為其着色，便產生左邊的圖像（${\displaystyle h(z)\triangleq 0}$）。內部黑色區域和外部是法圖元素，之間的邊界是${\displaystyle f}$的朱利亞集，有時稱為「考拉茲分形」。

指數插值的朱利亞集

還有許多方法可以定義復插值函數，如用復指數而非正餘弦：

${\displaystyle f(z)\triangleq {\frac {z}{2}}+{\frac {1}{4}}(2z+1)\left(1-e^{i\pi z}\right)}$,

它呈現出不同的動態。例如若${\displaystyle \operatorname {Im} (z)\gg 1}$，則${\displaystyle f(z)\approx z+{\tfrac {1}{4}}}$。對應的朱利亞集（如右圖）由不可數多的曲線組成，稱為「毛」或「線」。

優化

時空權衡

#作為奇偶序列一節給出了加快序列模擬的方法。要在每次迭代中向前跳轉k步，可將當前數字分成兩部分：b（k個最小有效位，解釋為整數）和a（剩餘位，解釋為整數）。向前跳轉k步的算法是

f^k(2^ka + b) = 3^{c(b, k)}a + d(b, k).

c（或更好的3^c）、d的值可針對所有可能的k位數b預先計算，其中d(b, k)是對b應用k次f函數的結果，c(b, k)是迭代過程中遇到的奇數個數。^[26]例如，若k = 5，那麼每次迭代都可以向前跳5步，方法是分理出數字的5個最小有效位，並使用

c(0...31, 5) = { 0, 3, 2, 2, 2, 2, 2, 4, 1, 4, 1, 3, 2, 2, 3, 4, 1, 2, 3, 3, 1, 1, 3, 3, 2, 3, 2, 4, 3, 3, 4, 5 },

d(0...31, 5) = { 0, 2, 1, 1, 2, 2, 2, 20, 1, 26, 1, 10, 4, 4, 13, 40, 2, 5, 17, 17, 2, 2, 20, 20, 8, 22, 8, 71, 26, 26, 80, 242 }.

這需要2^k的預計算和存儲，以將計算速度提高k倍，是時空權衡。

模限制

對於尋找考拉茲猜想反例，這種預計算帶來了更重要的加速。Tomás Oliveira e Silva在計算證實考拉茲猜想時，使用了這種加速，直到很大的n值。對給定的b、k，若不等式

f'^k(2^ka + b) = 3^c(b)a + d(b) < 2^ka + b

對所有a都成立，那麼第一個反例（若存在）不是b模2^k。^[27]例如，第一個反例一定是奇數，因為f(2n) = n小於2n；且一定是3 mod 4，因為f²(4n + 1) = 3n + 1，小於4n + 1。對每個不是考拉茲猜想反例的初值a，都存在使不等式成立的k，因此檢查起始值的考拉茲猜想，相當於檢查整個同餘類。隨着k增加，只需搜索沒有被較小的k消除的殘差b，將只剩極少數。^[4]例如，32模的殘差只有7、15、27、31。

錫拉丘茲函數

若k為奇整數，則3k + 1是偶數，所以3k + 1 = 2^ak′，k′是奇數且a ≥ 1。錫拉丘茲函數是從正整奇數集l指向自身的函數f，其中f(k) = k′ （OEIS數列A075677）。

錫拉丘茲函數的性質有：

• 對所有k ∈ I, f(4k + 1) = f(k)（因為3(4k + 1) + 1 = 12k + 4 = 4(3k + 1)。）
• 更通俗地說：對所有p ≥ 1和奇數h，f^{p − 1}(2^ph − 1) = 2 × 3^{p − 1}h − 1。（其中f^{p − 1}是函數迭代記號。）
• 對所有奇數h，f(2h − 1) ≤ 3h − 1/2

考拉茲猜想等價於：對l中所有k，存在整數n ≥ 1使fⁿ(k) = 1。

不可判定的推廣

主條目：FRACTRAN

1972年，約翰·康威證明了考拉茲猜想的一個自然推廣在算法上是不可判定的。^[28]

具體來說，他考慮了以下形式的函數 $${\displaystyle {g(n)=a_{i}n+b_{i}}{\text{ when }}{n\equiv i{\pmod {P}}},}$$ 其中a₀, b₀, ..., a_{P − 1}, b_{P − 1}是有理數，其選擇使g(n)總是整數。標準考拉茲函數為P = 2、a₀ = 1/2、b₀ = 0, a₁ = 3、b₁ = 1。康威證明

給定g、n，迭代序列g^k(n)是否能抵達1？

是不可判定的，可以轉化為停機問題。

與考拉茲猜想更接近的是下面這個普遍量化問題：

給定g，迭代序列g^k(n)對所有n > 0是否都能抵達1？

以這種方式修改條件，可以使問題變得更難或更易解決（直觀地說，正面答案更難證明，但反面答案可能更容易）。Kurtz & Simon^[29]證明，普遍量化問題事實上是不可判定的，在算術階層中甚至更高；具體地說，它是Π0
2完全的。即使將模數P限制在6840以限制函數g的類別，這難度結果也成立。^[30]

這種形式的簡化迭代（所有${\displaystyle b_{i}}$都為零）在一種名為FFRACTRAN的程式語言中得到了正式化。

研究歷史

在1930年代，德國漢堡大學的學生洛薩·考拉茲（英語：Lothar Collatz）曾經研究過這個猜想。在1960年，角谷靜夫（英語：Shizuo Kakutani）也研究過這個猜想。但這猜想到目前，仍沒有任何進展。

保羅·艾狄胥就曾稱，數學上尚未為此類問題提供答案。他並稱會替找出答案的人獎賞500元。

目前已經有分佈式計算在進行驗證。到2020年，已驗證正整數到${\displaystyle 2^{68}}$，也仍未有找到例外的情況。但是這並不能夠證明對於任何大小的數，這猜想都能成立。

有的數學家認為，該猜想任何程度的解決都是現代數學的一大進步，將開闢全新的領域。目前也有部分數學家和數學愛好者，在進行關於「負數的${\displaystyle 3x+1}$」、「${\displaystyle 5x+1}$」、「${\displaystyle 7x+1}$」等種種考拉茲猜想的變化形命題的研究。

2019年12月，陶哲軒證明只要${\displaystyle f(n)}$是一個趨於正無窮的實數列，那麼幾乎對所有的正整數${\displaystyle n}$（在對數密度意義下） ，有${\displaystyle S(n)<f(n)}$。^[31][32]

相關條目

• 數學主題

• 3x + 1半群

• 模算數
• 算術動力學

閱讀更多

• The Ultimate Challenge: The 3x + 1 Problem,^[3] 由美國數學學會於2010年出版，Jeffrey Lagarias編輯，是關於考拉茲猜想、處理方法和一般化思想的資料匯編。其中包含兩篇編者所撰的調查論文和5篇與其他作者撰寫的論文，內容涉及問題的歷史、一般化、統計方法與計算理論的結果。它還包含有關主題的早期論文的重印本，如洛薩·考拉茲的論文。

參考資料

1. Maddux, Cleborne D.; Johnson, D. Lamont. Logo: A Retrospective. New York: Haworth Press. 1997: 160. ISBN 0-7890-0374-0. The problem is also known by several other names, including: Ulam's conjecture, the Hailstone problem, the Syracuse problem, Kakutani's problem, Hasse's algorithm, and the Collatz problem.
2. Guy, Richard K. "E16: The 3x+1 problem". Unsolved Problems in Number Theory 3rd. Springer-Verlag. 2004: 330–6 [2023-11-12]. ISBN 0-387-20860-7. Zbl 1058.11001. （原始內容存檔於2024-01-21）.
3. Lagarias, Jeffrey C. (編). The Ultimate Challenge: The 3x + 1 Problem. American Mathematical Society. 2010. ISBN 978-0-8218-4940-8. Zbl 1253.11003.
4. Lagarias, Jeffrey C. The 3x + 1 problem and its generalizations. The American Mathematical Monthly. 1985, 92 (1): 3–23. JSTOR 2322189. doi:10.1080/00029890.1985.11971528.
5. Leavens, Gary T.; Vermeulen, Mike. 3x + 1 search programs. Computers & Mathematics with Applications. December 1992, 24 (11): 79–99. doi:10.1016/0898-1221(92)90034-F .
6. Roosendaal, Eric. 3x+1 delay records. [2020-03-14]. （原始內容存檔於2023-03-27）. (Note: "Delay records" are total stopping time records.)
7. Barina, David. Convergence verification of the Collatz problem. The Journal of Supercomputing. 2020, 77 (3): 2681–2688. S2CID 220294340. doi:10.1007/s11227-020-03368-x.
8. Garner, Lynn E. On the Collatz 3n + 1 algorithm. Proceedings of the American Mathematical Society. 1981, 82 (1): 19–22. JSTOR 2044308. doi:10.1090/S0002-9939-1981-0603593-2 .
9. Eliahou, Shalom. The 3x + 1 problem: new lower bounds on nontrivial cycle lengths. Discrete Mathematics. 1993, 118 (1): 45–56. doi:10.1016/0012-365X(93)90052-U .
10. Simons, J.; de Weger, B. Theoretical and computational bounds for m-cycles of the 3n + 1 problem (PDF). Acta Arithmetica. 2005, 117 (1): 51–70 [2023-11-12]. Bibcode:2005AcAri.117...51S. doi:10.4064/aa117-1-3 . （[35SidW-3n+1-ActaArith[2005].pdf 原始內容] (PDF)存檔於2022-03-18）.
11. Lagarias (1985) section "A heuristic argument".
12. Terras, Riho. A stopping time problem on the positive integers (PDF). Acta Arithmetica. 1976, 30 (3): 241–252 [2023-11-12]. MR 0568274. doi:10.4064/aa-30-3-241-252 . （原始內容存檔 (PDF)於2023-12-04）.
13. Tao, Terence. Almost all orbits of the Collatz map attain almost bounded values. Forum of Mathematics, Pi. 2022, 10: e12. ISSN 2050-5086. arXiv:1909.03562 . doi:10.1017/fmp.2022.8  （英語）.
14. Hartnett, Kevin. Mathematician Proves Huge Result on ‘Dangerous’ Problem. Quanta Magazine. 2019-12-11 [2023-11-12]. （原始內容存檔於2024-01-16）.
15. Krasikov, Ilia; Lagarias, Jeffrey C. Bounds for the 3x + 1 problem using difference inequalities. Acta Arithmetica. 2003, 109 (3): 237–258. Bibcode:2003AcAri.109..237K. MR 1980260. S2CID 18467460. arXiv:math/0205002 . doi:10.4064/aa109-3-4.
16. Hercher, C. There are no Collatz m-cycles with m <= 91 (PDF). Journal of Integer Sequences. 2023, 26 (3): Article 23.3.5 [2023-11-12]. （原始內容存檔 (PDF)於2023-12-08）.
17. Steiner, R. P. A theorem on the syracuse problem. Proceedings of the 7th Manitoba Conference on Numerical Mathematics. 1977: 553–9. MR 0535032.
18. Simons, John L. On the nonexistence of 2-cycles for the 3x + 1 problem. Math. Comp. 2005, 74: 1565–72. Bibcode:2005MaCom..74.1565S. MR 2137019. doi:10.1090/s0025-5718-04-01728-4 .
19. Colussi, Livio. The convergence classes of Collatz function. Theoretical Computer Science. 9 September 2011, 412 (39): 5409–5419. doi:10.1016/j.tcs.2011.05.056 .
20. Hew, Patrick Chisan. Working in binary protects the repetends of 1/3^h: Comment on Colussi's 'The convergence classes of Collatz function'. Theoretical Computer Science. 7 March 2016, 618: 135–141. doi:10.1016/j.tcs.2015.12.033 .
21. Lagarias, Jeffrey. The set of rational cycles for the 3x+1 problem. Acta Arithmetica. 1990, 56 (1): 33–53 [2023-11-12]. ISSN 0065-1036. doi:10.4064/aa-56-1-33-53 . （原始內容存檔於2023-03-27）.
22. Belaga, Edward G.; Mignotte, Maurice. Embedding the 3x+1 Conjecture in a 3x+d Context. Experimental Mathematics. 1998, 7 (2): 145–151 [2023-11-12]. S2CID 17925995. doi:10.1080/10586458.1998.10504364. （原始內容存檔於2023-06-09）.
23. Bernstein, Daniel J.; Lagarias, Jeffrey C. The 3x + 1 conjugacy map. Canadian Journal of Mathematics. 1996, 48 (6): 1154–1169. ISSN 0008-414X. doi:10.4153/CJM-1996-060-x  （英語）.
24. Chamberland, Marc. A continuous extension of the 3x + 1 problem to the real line. Dynam. Contin. Discrete Impuls Systems. 1996, 2 (4): 495–509.
25. Letherman, Simon; Schleicher, Dierk; Wood, Reg. The (3n + 1)-problem and holomorphic dynamics. Experimental Mathematics. 1999, 8 (3): 241–252. doi:10.1080/10586458.1999.10504402.
26. Scollo, Giuseppe. Looking for class records in the 3x + 1 problem by means of the COMETA grid infrastructure (PDF). Grid Open Days at the University of Palermo. 2007 [2023-11-12]. （原始內容存檔 (PDF)於2023-12-09）.
27. Garner, Lynn E. On the Collatz 3n + 1 algorithm. Proceedings of the American Mathematical Society. 1981, 82 (1): 19–22. JSTOR 2044308. doi:10.1090/S0002-9939-1981-0603593-2 .
28. Conway, John H. Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder: 49–52. 1972.
29. Kurtz, Stuart A.; Simon, Janos. The undecidability of the generalized Collatz problem. Cai, J.-Y.; Cooper, S. B.; Zhu, H. (編). Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. 2007: 542–553. ISBN 978-3-540-72503-9. doi:10.1007/978-3-540-72504-6_49. As PDF
30. Ben-Amram, Amir M. Mortality of iterated piecewise affine functions over the integers: Decidability and complexity. Computability. 2015, 1 (1): 19–56. doi:10.3233/COM-150032.
31. Kevin Hartnett. Mathematician Proves Huge Result on ‘Dangerous’ Problem. Quantamagazine. 2019-12-11 [2019-12-16]. （原始內容存檔於2020-06-18）.
32. Terence Tao. Almost all orbits of the Collatz map attain almost bounded values. arXiv. 2019-09-13 [2019-12-16]. （原始內容存檔於2021-04-17）.

外部連結

• 以電腦研究考拉茲猜想的網頁 （頁面存檔備份，存於互聯網檔案館）
• Collatz Conjecture的BOINC專案網頁 （頁面存檔備份，存於互聯網檔案館）
• Matthews, Keith. 3 x + 1 page. [2023-11-12]. （原始內容存檔於2022-11-03）.
• An ongoing volunteer computing project 互聯網檔案館的存檔，存檔日期2021-08-30. by David Bařina verifies Convergence of the Collatz conjecture for large values. (furthest progress so far)
• An ongoing volunteer computing project （頁面存檔備份，存於互聯網檔案館） by Eric Roosendaal verifies the Collatz conjecture for larger and larger values.
• Another ongoing volunteer computing project （頁面存檔備份，存於互聯網檔案館） by Tomás Oliveira e Silva continues to verify the Collatz conjecture (with fewer statistics than Eric Roosendaal's page but with further progress made).
• 埃里克·韋斯坦因. Collatz Problem. MathWorld.
• Collatz Problem at PlanetMath..
• Nochella, Jesse. Collatz Paths. Wolfram Demonstrations Project. [2023-11-12]. （原始內容存檔於2023-12-04）.
• Eisenbud, D. Uncrackable? The Collatz conjecture (short video). Numberphile. 2016-08-08. （原始內容存檔於2021-12-11） –透過YouTube.
• Eisenbud, D. Uncrackable? Collatz conjecture (extra footage). Numberphile. 2016-08-09. （原始內容存檔於2021-12-11） –透過YouTube.
• Alex Kontorovich​（德語） (featuring). The simplest math problem no one can solve (short video). Veritasium. 2021-07-30 [2023-11-12]. （原始內容存檔於2024-03-14） –透過YouTube.
• Are computers ready to solve this notoriously unwieldy math problem? （頁面存檔備份，存於互聯網檔案館）