考拉兹猜想

Template:NoteTA Template:Unsolved 考拉兹猜想（Template:Lang-en），又称为奇偶归一猜想、3n+1猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想，是指对于每一个正整数，如果它是奇数，则对它乘3再加1，如果它是偶数，则对它除以2，如此循环，最终都能够得到1。

$f(n)=\{\begin{array}{cc}n/2& \text{if }n\equiv 0\\ 3n+1& \text{if }n\equiv 1\end{array}(\mathrm{mod}2).$

埃尔德什·帕尔在谈到考拉兹猜想时说：“数学还没准备好应对这样的问题。”Template:Le指出，考拉兹猜想“是个异常困难的问题，完全超出了当今数学的范围”。

问题表述

1到9999的数字及其相应的停止时间

1到10⁸的总停止时间直方图，x轴为总停止时间，y轴为频率。

1到10⁹的总停止时间柱状图直方图，x轴为总停止时间，y轴为频率。

2到10⁷的迭代时间

总停止时间：最高250、1000、4000、20000、100000、500000的数字

对任意正整数进行以下运算；

• 若为偶数，则除以2；
• 若为奇数，则将其×3再加1。

这可以定义为模算术函数Template:Mvar： $$f(n)=\{\begin{array}{cc}n/2& \text{if }n\equiv 0(\mathrm{mod}2),\\ [4px]3n+1& \text{if }n\equiv 1(\mathrm{mod}2).\end{array}$$

现重复执行该运算，形成一个序列，从任意正整数开始，把每步的结果作为下一步的输入。可记作： $$a_i=\{\begin{array}{cc}n& \text{for }i=0,\\ f(a_{i-1})& \text{for }i>0\end{array}$$ （即：Template:Math是递归Template:Mvar次应用于Template:Mvar的Template:Mvar值；Template:Math）。

考拉兹猜想是：所有正整数最终都会到达1，即存在i使得Template:Math。

若猜想为假，表示存在某个初值产生一个不含1的循环数列，或朝無窮大發散的數列，目前尚未发现这样的数列。

最小的使Template:Math的Template:Mvar称为Template:Mvar的停止时间，相似地，使Template:Math的最小的Template:Mvar称为Template:Mvar的总停止时间。若索引Template:Mvar或Template:Mvar的其中一个不存在，就称停止时间或总停止时间分别不存在。

考拉兹猜想认为，所有Template:Mvar的总停止时间都是有限的，即所有Template:Math都有有限的停止时间。

只要Template:Mvar是奇数，Template:Math就是偶数，所以可以使用考拉兹函数的“快捷”形式： $$f(n)=\{\begin{array}{cc}\frac{n}{2}& \text{if }n\equiv 0(\mathrm{mod}2),\\ [4px]\frac{3n+1}{2}& \text{if }n\equiv 1(\mathrm{mod}2).\end{array}$$ 这个定义可在过程整体动态不变的前提下，获得较小的停止时间和总停止时间值。

经验数据

取一个正整数：

• 如$n$ = 6，根据上述数式，得出序列6, 3, 10, 5, 16, 8, 4, 2, 1。（步驟中最高的數是16，共有8個步驟）
• 如$n$ = 11，根据上述数式，得出序列11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。（步驟中最高的數是52，共有14個步驟）
• 如$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個步驟）Template:OEIS

奇偶归一猜想称，任何正整数，经过上述计算步骤後，最终都会得到1。

$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, ... Template:OEIS

最大轨迹点大于任何较小起始值的起始值构成如下序列

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, ... Template:OEIS

Template:Mvar达到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, ... Template:OEIS

总停止时间最长，且

小于10的是9，经历19步；

小于100的是97，经历118步；

小于1000的是871，经历178步；

小于10⁴的是6171，经历261步；

小于10⁵的是Template:Val，经历350步；

小于10⁶的是Template:Val，经历524步；

小于10⁷的是Template:Val，经历685步；

小于10⁸的是Template:Val，经历949步；

小于10⁹的是Template:Val，经历986步；

小于10¹⁰的是Template:Val，经历1132步；

小于10¹¹的是Template:Val，经历1228步；

小于10¹²的是Template:Val，经历1348步；…… Template:OEIS

这些数字也是具有指定步数的最低数字，但不一定是唯一的，例如经历1132步的有Template:Val，还有Template:Val。

与位数（以2为基）相关的总停止时间最小的起始值是2的幂，因为Template:Math经历Template:Mvar次减半才达到1，且永远不会增加。

可视化

• 
  前1000个数的轨迹的有向图
• 
  Template:Mvar轴表示初始数，Template:Mvar轴表示到1过程中到达的最大值。此图显示了压缩的Template:Mvar轴：有些Template:Mvar值产生的轨迹最大值可达Template:Val（Template:Math）
• 
  与左图相同，但采用对数坐标，显示了所有Template:Mvar值。图中间的第一条粗线对应27处的尖端，在9232到达最大值
• 
  小于20步的所有数集合
• 
  前1亿个数到达1的迭代次数

支持论据

虽然猜想尚未得到证实，但大多数数学家都认为它是真的，因为实验证据和启发式论证都支持这一猜想。

实验证据

截至2020年，已经用计算机验证了2⁶⁸ ≈ Template:Val之前的所有初始值，最终都以周期为3的循环Template:Math作结。

显然，这不能证明猜想对所有初始值都正确，因为非常大的正整数可能会出现反例，例如希爾伯特－波利亞猜想的反例。不过，这种验证可能会产生其他影响，例如我们可以推导出关于非平凡周期和结构形式的额外约束。Template:Clarify

概率启发式

若只考虑考拉兹过程产生序列中的奇数，那么每个奇数平均都是前一个的Template:Sfrac。Template:Refn（更准确地说，结果的几何均值是Template:Sfrac。）这就产生了启发式论证：每个考拉兹序列从长期来看都倾向于减小，虽然这不能证明不存在其他的周期。这个论证不是证明，因为它假定考拉兹序列是由不相关的概率事件组合而成的。（确实严格证明了考拉兹过程的2进数推广在几乎所有初始值的每个乘法步骤都对应两个除法步骤）

停止时间

正如Riho Terras证明，几乎每个正整数都有有限的停止时间。换句话说，几乎每个考拉兹序列都会到达严格低于其初值的点。该证明基于奇偶向量的分布，并利用了中心极限定理。

2019年，陶哲轩利用概率密度函数改进了这一结果，证明几乎所有（对数密度意义上的）考拉兹轨道都在起点的任意发散函数之下。《量子杂志》在回应这项工作时写道，陶哲轩“获得了几十年来关于考拉兹猜想的最重要成果之一”。

下界

Krasikov & Lagarias在一份计算机辅助证明中证明，对所有足够大的Template:Mvar，区间Template:Math中最终达到1的整数个数至少等于Template:Math。

循环

在这一节中，考虑考拉兹函数的快捷形式 $$f(n)=\{\begin{array}{cc}\frac{n}{2}& \text{if }n\equiv 0(\mathrm{mod}2),\\ [4px]\frac{3n+1}{2}& \text{if }n\equiv 1(\mathrm{mod}2).\end{array}$$ 循环是由不同正整数组成的序列Template:Math，其中Template:Math, Template:Math, ..., Template:Math。

唯一已知的循环是周期为2的Template:Math，称作平凡循环。

周期长度

非平凡周期的长度至少为Template:Val。若能证明对所有小于$3\times 2^{69}$的正整数，考拉兹序列都收敛到1，则这个下界就会提高到Template:Val。实际上，Eliahou (1993)证明了任何非平凡循环的周期Template:Mvar的形式为 $$p=301994a+17087915b+85137581c$$ 其中Template:Mvar、Template:Mvar、Template:Mvar为非负整数，Template:Math，Template:Math。这个结果是基于Template:Math的连分数展开。

Template:Mvar循环

Template:Mvar循环是可分为Template:Math段连续子列的循环，每个子列由奇数的递增序列和偶数的递减序列组成。例如，若循环由1个奇数的递增序列和偶数的递减序列组成，则称为1循环。

Steiner (1977)证明，除平凡循环Template:Math外不存在其他1循环。Simons (2005)用Steiner的方法证明没有2循环。 Simons & de Weger (2005)将这一证明推广到68循环，即Template:Math以下不存在Template:Mvar循环。Hercher进一步推广了这一方法，证明不存在Template:Math的k循环。随着计算机穷举搜索的继续，可能会排除更大的Template:Math值。

猜想的其他表述

反向

自下而上生成的考拉兹图的前21层。包含所有轨道长度小于等于21的数字

还有另一种方法可证明这猜想：采用自下而上的方法构造所谓考拉兹图，由逆关系定义： $$R(n)=\{\begin{array}{cc}\{2n\}& \text{if }n\equiv 0,1,2,3,5\\ [4px]\{2n,\frac{n-1}{3}\}& \text{if }n\equiv 4\end{array}(\mathrm{mod}6).$$

因此，与其证明所有正整数都指向1，我们可以尝试证明1指向所有正整数。对任意整数Template:Mvar，Template:Math当且仅当Template:Math。等价地，Template:Math当且仅当Template:Math。根据猜想，除了1-2-3循环之外，这个逆关系构成一棵树。

函数Template:Mvar的关系式Template:Math可用“快捷”关系式Template:Math代替，则考拉兹图由逆关系定义： $$R(n)=\{\begin{array}{cc}\{2n\}& \text{if }n\equiv 0,1\\ [4px]\{2n,\frac{2n-1}{3}\}& \text{if }n\equiv 2\end{array}(\mathrm{mod}3).$$

对任意整数Template:Mvar，Template:Math当且仅当Template:Math。等价地，Template:Math当且仅当Template:Math。根据猜想，除了1-2循环之外，这个逆关系构成一棵树。

或者，把Template:Math换成Template:Math，其中Template:Math、Template:Math是整除Template:Math的最大的2的幂，得到的函数Template:Mvar将从奇数映射到奇数。现假设对某个奇数Template:Mvar，进行Template:Mvar次运算会得到数字1（即Template:Math）。则数字Template:Mvar在二进制中可写为字符串Template:Math，其中每个Template:Math都是从Template:Math的表示中提取的有限连续字符串。因此，Template:Mvar的表示包含了除Template:Math的重复尾数，每个重复尾数可以选择旋转，再复制到有限位数。只有二进制会出现这种情况。根据猜想，每个以“1”结尾的二进制字符串Template:Mvar都可用这种形式表示（可以添加或删除Template:Mvar的前导0）。

作为以二进制计算的抽象机

考拉兹函数的重复应用可用处理比特串的抽象机表示。它会对任何奇数执行以下3步，直到只剩一个1:

1. 在二进制数的（右）端加Template:Mono（得到Template:Math）；
2. 用二进制加法将其加到原数上（Template:Math）；
3. 去掉所有尾数Template:Mono（反复除以2直到结果为奇数）。

示例

起始值为7，以二进制写作Template:Mono。得到的考拉兹序列为：

         111
        1111
       10110
      10111
     100010
    100011
    110100
   11011
  101000
 1011
10000

作为奇偶序列

本节中，考虑略微修改的考拉兹函数 $$f(n)=\{\begin{array}{cc}\frac{n}{2}& \text{if }n\equiv 0\\ [4px]\frac{3n+1}{2}& \text{if }n\equiv 1\end{array}(\mathrm{mod}2).$$

这样做是因为Template:Mvar为奇数时，Template:Math总是偶数。

若Template:Math表示某数的奇偶性，例如Template:Math、Template:Math，则可定义一个数Template:Mvar的考拉兹奇偶序列Template:Math，其中Template:Math；Template:Math。

执行Template:Math还是Template:Math的哪种运算取决于奇偶性，序列与运算序列相同。

利用Template:Math的这种形式，可证明两个数Template:Mvar、Template:Mvar的奇偶性序列在前Template:Mvar项上一致，当且仅当Template:Mvar、Template:Mvar是等价的模Template:Math。这意味着每个数都能通过奇偶性序列唯一识别，此外若存在多个考拉兹循环，则它们对应的奇偶性循环也一定是不同的。

对数Template:Math应用Template:Mvar次Template:Mvar函数，得到Template:Math，其中Template:Mvar是对Template:Mvar应用Template:Mvar次Template:Mvar函数的结果，Template:Mvar是在序列中增加的次数。例如，对于Template:Math，1依次上升到2、1、2、1，最后上升到2时有3次上升，因此结果是Template:Math；对于Template:Math只有一次上升：1、2、1，所以结果是Template:Math。Template:Mvar是Template:Math时，会有Template:Mvar次上升，结果是Template:Math。3的幂乘Template:Mvar与Template:Mvar无关，只取决于Template:Mvar的行为，这使我们可以预测，某些形式的数在迭代一定次数后总会到达更小的数字，例如Template:Math在应用两次Template:Mvar后会变成Template:Math，Template:Math应用4次会变成Template:Math。不过，这些小数是否继续下降到1则取决于Template:Mvar的值。

作为标记系统

对于形式为

$f(n)=\{\begin{array}{cc}\frac{n}{2}& \text{if }n\equiv 0\\ [4px]\frac{3n+1}{2}& \text{if }n\equiv 1.\end{array}(\mathrm{mod}2)$

的考拉兹函数，考拉兹序列可通过2标记系统计算，生成规则为

Template:Math, Template:Math, Template:Math.

系统中，正整数Template:Mvar由包含Template:Mvar份Template:Mvar的字符串表示，标签操作的迭代在热河长度小于2的词上停止（改编自De Mol）。

考拉兹猜想等价地指出，以任意有限的Template:Mvar字符串作为初值，标记系统最终会停止。

推广

在所有整数上迭代

考拉兹猜想的扩展是包含所有整数，而不仅仅是正整数。撇开无法从外部进入的0→0循环，已知循环共有4个，所有非零整数似乎都会在Template:Mvar的迭代下陷入其中：

奇数值用大粗体表示，每个循环以其绝对值最小的成员（总是奇数）为先列出。

循环	奇数值循环长度	全循环长度
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

推广的考拉兹猜想：在Template:Mvar的迭代下，所有整数最终都会落入上述4个循环或0→0循环中的一个。

奇分母有理数的迭代

考拉兹映射可扩展到奇分母的有理数。根据分子的奇偶，可将有理数分奇偶，然后映射公式与域为整数时完全相同：偶有理数除以2，奇有理数乘以3再加1。一个密切相关的事实是，考拉兹猜想可推广到2进整数，其中包含作为子环的奇分母有理数环。

运用“快捷”函数时，已知任何周期的奇偶性序列都恰好由一个有理数生成。相反，有人猜想，每个奇分母有理数都有最终循环的奇偶性序列（周期性猜想)）。

若奇偶循环长为Template:Mvar，且在Template:Math处包含了Template:Mvar次奇数，那么立即周期性地产生奇偶循环的唯一有理数： Template:NumBlk

例如，奇偶循环Template:Nowrap长度为7，4个奇数项分别位于0、2、3、6处。它由分数 $$\frac{3^3{2}^0+3^2{2}^2+3^1{2}^3+3^0{2}^6}{2^7-3^4}=\frac{151}{47}$$ 因为后者可产生有理循环 $$\frac{151}{47}\to \frac{250}{47}\to \frac{125}{47}\to \frac{211}{47}\to \frac{340}{47}\to \frac{170}{47}\to \frac{85}{47}\to \frac{151}{47}.$$

Template:Nowrap的任何循环排列都与上述分数之一相关。例如，循环Template:Nowrap可由下面的分数产生 $$\frac{3^3{2}^1+3^2{2}^2+3^1{2}^5+3^0{2}^6}{2^7-3^4}=\frac{250}{47}.$$

为实现一一对应，奇偶循环应是不可还原的，即无法分割成相同的子循环。例如，奇偶循环Template:Nowrap及其子循环Template:Nowrap在化为最小项时与相同的分数Template:Sfrac相关。

这时，假设考拉兹猜想成立，就意味着Template:Nowrap、Template:Nowrap是唯一由正整数（1、2）产生的奇偶性循环。

若有理数的奇分母Template:Mvar不是3的倍数，则所有迭代数都将有相同的分母，通过应用考拉兹函数的Template:Math推广，可得考拉兹函数 $$T_d(x)=\{\begin{array}{cc}\frac{x}{2}& \text{if }x\equiv 0(\mathrm{mod}2),\\ [4px]\frac{3x+d}{2}& \text{if }x\equiv 1(\mathrm{mod}2).\end{array}$$

2进数推广

函数 $$T(x)=\{\begin{array}{cc}\frac{x}{2}& \text{if }x\equiv 0(\mathrm{mod}2)\\ [4px]\frac{3x+1}{2}& \text{if }x\equiv 1(\mathrm{mod}2)\end{array}$$ 在2进整环${\mathbb{Z}}_2$上有精确定义，是连续的，且关于2进度量是保测的。另外，已知其动态是遍历的。

定义作用于${\mathbb{Z}}_2$的奇偶矢量函数Template:Mvar： $$Q(x)=\sum _{k=0}^{\mathrm{\infty }}(T^k(x)mod2)2^k.$$

函数Template:Mvar是2进等距同构。因此，每个无限奇偶性序列都恰好出现一恶搞2进整数，所以几乎所有轨迹在${\mathbb{Z}}_2$中都是非循环的。

考拉兹猜想的等价表述是 $$Q\left({\mathbb{Z}}^{+}\right)\subset \frac{1}{3}\mathbb{Z}.$$

在实数、复数上的迭代Template:Anchor

10 → 5 → 8 → 4 → 2 → 1 → ..迭代轨迹的蜘蛛图。运用了推广到实数的考拉兹映射。

$x$为整偶数时$x/2$、为整奇数时$3x+1$或$(3x+1)/2$（“快捷”版本）的函数，可将考拉兹映射推广到实數，这就是所谓的插值函数。一个简单方法是选取两个函数$g_1$、$g_2$，其中

$g_1(n)=\{\begin{array}{cc}1,& n\text{ is even,}\\ 0,& n\text{ is odd,}\end{array}$

$g_2(n)=\{\begin{array}{cc}0,& n\text{ is even,}\\ 1,& n\text{ is odd,}\end{array}$

并将它们作为我们所需值的开关：

$f(x)\triangleq \frac{x}{2}\cdot g_1(x)+\frac{3x+1}{2}\cdot g_2(x)$.

其中一个选择是$g_1(x)\triangleq {\cos }^2\left(\frac{\pi }{2}x\right)$、$g_2(x)\triangleq {\sin }^2\left(\frac{\pi }{2}x\right)$。这映射的迭代产生了动力系统，Marc Chamberland对其进行了进一步研究。他证明这个猜想对于正实数不成立，因为存在无穷多个不动点与无穷多单调发散到无穷的轨道。函数$f$有2个周期为$2$的吸引子循环：$(1;2)$、$(1.1925...;2.1386...)$。此外，我们猜想无界轨道集的勒贝格测度为$0$。

Letherman、Schleicher和Wood将研究推广到复平面，用张伯伦函数求解复正余弦，并添加了额外项$\frac{1}{\pi }(\frac{1}{2}-\cos (\pi z))\sin (\pi z)+$ $h(z){\sin }^2(\pi z)$，其中$h(z)$是任意整函数。由于该式对整实数求值为零，所以推广函数

$\begin{array}{cc}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 }(\frac{1}{2}-\cos (\pi z))\sin (\pi z)+h(z){\sin }^2(\pi z)\end{array}$

是考拉兹映射到复平面的插值。添加额外项将所有整数都变为$f$的临界点，于是可证明没有一个整数位于Baker域中，意味着任何整数或者是周期性的，或者属于游荡域。他们猜想后者不成立，也就可以导出，所有整数轨都是有限的。

以原点为中心的考拉兹分形，实部为-5到5。

大部分点的轨道发散，根据发散速度为其着色，便产生左边的图像（$h(z)\triangleq 0$）。内部黑色区域和外部是法图元素，之间的边界是$f$的朱利亚集，有时称为“考拉兹分形”。

指数插值的朱利亚集

还有许多方法可以定义复插值函数，如用复指数而非正余弦：

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

它呈现出不同的动态。例如若$\mathrm{Im}(z)\gg 1$，则$f(z)\approx z+\frac{1}{4}$。对应的朱利亚集（如右图）由不可数多的曲线组成，称为“毛”或“线”。

优化

时空权衡

#作为奇偶序列一节给出了加快序列模拟的方法。要在每次迭代中向前跳转Template:Mvar步，可将当前数字分成两部分：Template:Mvar（Template:Mvar个最小有效位，解释为整数）和Template:Mvar（剩余位，解释为整数）。向前跳转Template:Mvar步的算法是

Template:Math.

Template:Mvar（或更好的Template:Math）、Template:Mvar的值可针对所有可能的Template:Mvar位数Template:Mvar预先计算，其中Template:Math是对Template:Mvar应用Template:Mvar次Template:Mvar函数的结果，Template:Math是迭代过程中遇到的奇数个数。例如，若Template:Math，那么每次迭代都可以向前跳5步，方法是分理出数字的5个最小有效位，并使用

Template:Mvar(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 },

Template:Mvar(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 }.

这需要Template:Math的预计算和存储，以将计算速度提高Template:Mvar倍，是时空权衡。

模限制

对于寻找考拉兹猜想反例，这种预计算带来了更重要的加速。Tomás Oliveira e Silva在计算证实考拉兹猜想时，使用了这种加速，直到很大的Template:Mvar值。对给定的Template:Mvar、Template:Mvar，若不等式

Template:Math

对所有Template:Mvar都成立，那么第一个反例（若存在）不是Template:Mvar模Template:Math。例如，第一个反例一定是奇数，因为Template:Math小于Template:Math；且一定是3 mod 4，因为Template:Math，小于Template:Math。对每个不是考拉兹猜想反例的初值Template:Mvar，都存在使不等式成立的Template:Mvar，因此检查起始值的考拉兹猜想，相当于检查整个同余类。随着Template:Mvar增加，只需搜索没有被较小的Template:Mvar消除的残差Template:Mvar，将只剩极少数。例如，32模的残差只有7、15、27、31。

锡拉丘兹函数

若Template:Mvar为奇整数，则Template:Math是偶数，所以Template:Math，Template:Math是奇数且Template:Math。锡拉丘兹函数是从正整奇数集Template:Mvar指向自身的函数Template:Mvar，其中Template:Math Template:OEIS。

锡拉丘兹函数的性质有：

• 对所有Template:Math, Template:Math（因为Template:Math。）
• 更通俗地说：对所有Template:Math和奇数Template:Mvar，Template:Math。（其中Template:Math是函数迭代记号。）
• 对所有奇数Template:Mvar，Template:Math

考拉兹猜想等价于：对Template:Mvar中所有Template:Mvar，存在整数Template:Math使Template:Math。

不可判定的推广

Template:Main 1972年，约翰·康威证明了考拉兹猜想的一个自然推广在算法上是不可判定的。

具体来说，他考虑了以下形式的函数 $$g(n)=a_{i}n+b_i\text{ when }n\equiv i(\mathrm{mod}P),$$ 其中Template:Math是有理数，其选择使Template:Math总是整数。标准考拉兹函数为Template:Math、Template:Math、Template:Math, Template:Math、Template:Math。康威证明

给定Template:Mvar、Template:Mvar，迭代序列Template:Math是否能抵达Template:Math？

是不可判定的，可以转化为停机问题。

与考拉兹猜想更接近的是下面这个普遍量化问题：

给定Template:Mvar，迭代序列Template:Math对所有Template:Math是否都能抵达Template:Math？

以这种方式修改条件，可以使问题变得更难或更易解决（直观地说，正面答案更难证明，但反面答案可能更容易）。Kurtz & Simon证明，普遍量化问题事实上是不可判定的，在算术阶层中甚至更高；具体地说，它是Template:Math完全的。即使将模数Template:Mvar限制在6840以限制函数Template:Mvar的类别，这难度结果也成立。

这种形式的简化迭代（所有$b_i$都为零）在一种名为FFRACTRAN的编程语言中得到了正式化。

研究历史

在1930年代，德国汉堡大学的学生洛薩·考拉兹曾经研究过这个猜想。在1960年，Template:Le也研究过这个猜想。但这猜想到目前，仍没有任何进展。

保羅·艾狄胥就曾称，数学上尚未为此类问题提供答案。他并称会替找出答案的人奖赏500元。

目前已经有分布式计算在进行验证。到2020年，已验证正整数到$2^{68}$，也仍未有找到例外的情况。但是这并不能够证明对於任何大小的数，这猜想都能成立。

有的数学家认为，该猜想任何程度的解决都是现代数学的一大进步，将开辟全新的领域。目前也有部分数学家和数学爱好者，在进行关于“负数的$3x+1$”、“$5x+1$”、“$7x+1$”等種種考拉兹猜想的變化形命題的研究。

2019年12月，陶哲轩证明只要$f(n)$是一个趋于正无穷的实数列，那么几乎对所有的正整数$n$（在对数密度意义下） ，有$S(n)<f(n)$。

相關條目

• 3x + 1半群

• 模算數
• 算术动力学

阅读更多

• The Ultimate Challenge: The Template:Nobr Problem, 由美国数学学会于2010年出版，Jeffrey Lagarias编辑，是关于考拉兹猜想、处理方法和一般化思想的资料汇编。其中包含两篇编者所撰的调查论文和5篇与其他作者撰写的论文，内容涉及问题的历史、一般化、统计方法与计算理论的结果。它还包含有关主题的早期论文的重印本，如洛萨·考拉兹的论文。

外部連結

• 以電腦研究考拉兹猜想的網頁 Template:Wayback
• Collatz Conjecture的BOINC專案網頁 Template:Wayback
• Template:Cite web
• An ongoing volunteer computing project Template:Webarchive by David Bařina verifies Convergence of the Collatz conjecture for large values. (furthest progress so far)
• An ongoing volunteer computing project Template:Wayback by Eric Roosendaal verifies the Collatz conjecture for larger and larger values.
• Another ongoing volunteer computing project Template:Wayback 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).
• Template:MathWorld
• Template:PlanetMath.
• Template:Cite web
• Template:Cite AV mediaTemplate:Cbignore
• Template:Cite AV mediaTemplate:Cbignore
• Template:Cite AV media
• Are computers ready to solve this notoriously unwieldy math problem? Template:Wayback