考拉兹猜想

未解決的數學問題：對所有正整数，如果它是奇數，則對它乘3再加1，如果它是偶數，則對它除以2，如此循環，最終都能夠得到1。

考拉兹猜想（英語：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(2010)指出，考拉兹猜想“是个异常困难的问题，完全超出了当今数学的范围”。^[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。

若猜想为假，则只可能因为存在某个初值产生一个不含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][需要解释]}

概率启发式

若只考虑考拉兹过程产生序列中的奇数，那么每个奇数平均都是前一个的{{sfrac|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. ISBN 0-387-20860-7. Zbl 1058.11001. 
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].  (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. SidW-3n+1-ActaArith[2005].pdf Theoretical and computational bounds for m-cycles of the 3n + 1 problem] (PDF). Acta Arithmetica. 2005, 117 (1): 51–70. Bibcode:2005AcAri.117...51S. doi:10.4064/aa117-1-3  . 
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. MR 0568274. doi:10.4064/aa-30-3-241-252  . 
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. 
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. 
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. ISSN 0065-1036. doi:10.4064/aa-56-1-33-53  . 
22. Belaga, Edward G.; Mignotte, Maurice. Embedding the 3x+1 Conjecture in a 3x+d Context. Experimental Mathematics. 1998, 7 (2): 145–151. S2CID 17925995. doi:10.1080/10586458.1998.10504364. 
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. 
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. . Quantamagazine. 2019-12-11 [2019-12-16]. （原始内容存档于2020-06-18）. 
32. Terence Tao. . arXiv. 2019-09-13 [2019-12-16]. （原始内容存档于2021-04-17）. 

外部連結

• 以電腦研究考拉兹猜想的網頁 （页面存档备份，存于互联网档案馆）
• Collatz Conjecture的BOINC專案網頁 （页面存档备份，存于互联网档案馆）
• Matthews, Keith. 3 x + 1 page. 
• 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. 
• 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 –通过YouTube. 
• Are computers ready to solve this notoriously unwieldy math problem?