考拉兹猜想

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

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

问题表述
alt=Total Stopping Time: numbers up to 250, 1000, 4000, 20000, 100000, 500000|thumb|总停止时间：最高250、1000、4000、20000、100000、500000的数字
对任意正整数进行以下运算；

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

这可以定义为模算术函数：

现重复执行该运算，形成一个序列，从任意正整数开始，把每步的结果作为下一步的输入。可记作：

（即：是递归次应用于的值；）。

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

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

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

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

只要是奇数，就是偶数，所以可以使用考拉兹函数的“快捷”形式：

这个定义可在过程整体动态不变的前提下，获得较小的停止时间和总停止时间值。

经验数据

取一个正整数：
 如 = 6，根据上述数式，得出序列6, 3, 10, 5, 16, 8, 4, 2, 1。（步驟中最高的數是16，共有8個步驟）
 如 = 11，根据上述数式，得出序列11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。（步驟中最高的數是52，共有14個步驟）
 如 = 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個步驟）
奇偶归一猜想称，任何正整数，经过上述计算步骤後，最终都会得到1。

500px|thumb|center|=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, ... 

最大轨迹点大于任何较小起始值的起始值构成如下序列
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, ... 

达到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, ... 

总停止时间最长，且
小于10的是9，经历19步；
小于100的是97，经历118步；
小于1000的是871，经历178步；
小于104的是6171，经历261步；
小于105的是，经历350步；
小于106的是，经历524步；
小于107的是，经历685步；
小于108的是，经历949步；
小于109的是，经历986步；
小于1010的是，经历1132步；
小于1011的是，经历1228步；
小于1012的是，经历1348步；…… (Note: "Delay records" are total stopping time records.)

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

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

可视化

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

实验证据
截至2020年，已经用计算机验证了268 ≈ 之前的所有初始值，最终都以周期为3的循环作结。

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

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

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

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

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

循环
在这一节中，考虑考拉兹函数的快捷形式

循环是由不同正整数组成的序列，其中, , ..., 。

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

周期长度
非平凡周期的长度至少为。若能证明对所有小于的正整数，考拉兹序列都收敛到1，则这个下界就会提高到。实际上，Eliahou (1993)证明了任何非平凡循环的周期的形式为

其中、、为非负整数，，。这个结果是基于的连分数展开。

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

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

猜想的其他表述
反向
还有另一种方法可证明这猜想：采用自下而上的方法构造所谓考拉兹图，由逆关系定义：

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

函数的关系式可用“快捷”关系式代替，则考拉兹图由逆关系定义：

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

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

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

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

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

          111
         1111
        10110
       10111
      100010
     100011
     110100
    11011
   101000
  1011
 10000

作为奇偶序列
本节中，考虑略微修改的考拉兹函数

这样做是因为为奇数时，总是偶数。

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

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

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

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

作为标记系统
对于形式为

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

, , .

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

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

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

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

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

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

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

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

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

例如，奇偶循环长度为7，4个奇数项分别位于0、2、3、6处。它由分数

因为后者可产生有理循环

的任何循环排列都与上述分数之一相关。例如，循环可由下面的分数产生

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

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

若有理数的奇分母不是3的倍数，则所有迭代数都将有相同的分母，通过应用考拉兹函数的推广，可得考拉兹函数

2进数推广
函数

在2进整环上有精确定义，是连续的，且关于2进度量是保测的。另外，已知其动态是遍历的。

定义作用于的奇偶矢量函数：

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

考拉兹猜想的等价表述是

在实数、复数上的迭代

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

并将它们作为我们所需值的开关：
.
其中一个选择是、。这映射的迭代产生了动力系统，Marc Chamberland对其进行了进一步研究。他证明这个猜想对于正实数不成立，因为存在无穷多个不动点与无穷多单调发散到无穷的轨道。函数有2个周期为的吸引子循环：、。此外，我们猜想无界轨道集的勒贝格测度为。

Letherman、Schleicher和Wood将研究推广到复平面，用张伯伦函数求解复正余弦，并添加了额外项
，其中是任意整函数。由于该式对整实数求值为零，所以推广函数

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


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


还有许多方法可以定义复插值函数，如用复指数而非正余弦：
,
它呈现出不同的动态。例如若，则。对应的朱利亚集（如右图）由不可数多的曲线组成，称为“毛”或“线”。

优化
时空权衡
#作为奇偶序列一节给出了加快序列模拟的方法。要在每次迭代中向前跳转步，可将当前数字分成两部分：（个最小有效位，解释为整数）和（剩余位，解释为整数）。向前跳转步的算法是
.
（或更好的）、的值可针对所有可能的位数预先计算，其中是对应用次函数的结果，是迭代过程中遇到的奇数个数。例如，若，那么每次迭代都可以向前跳5步，方法是分理出数字的5个最小有效位，并使用

 (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 },
 (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 }.

这需要的预计算和存储，以将计算速度提高倍，是时空权衡。
模限制
对于寻找考拉兹猜想反例，这种预计算带来了更重要的加速。Tomás Oliveira e Silva在计算证实考拉兹猜想时，使用了这种加速，直到很大的值。对给定的、，若不等式

{{math|fk(2ka + b)   3c(b)a + d(b) < 2ka + b}}

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

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

锡拉丘兹函数的性质有：

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

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

 不可判定的推广 

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

具体来说，他考虑了以下形式的函数

其中是有理数，其选择使总是整数。标准考拉兹函数为、、, 、。康威证明

 给定、，迭代序列是否能抵达？

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

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

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

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

这种形式的简化迭代（所有都为零）在一种名为FFRACTRAN的编程语言中得到了正式化。
研究历史
在1930年代，德国汉堡大学的学生洛薩·考拉兹曾经研究过这个猜想。在1960年，也研究过这个猜想。但这猜想到目前，仍没有任何进展。

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

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

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

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

相關條目

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

 外部連結 
 以電腦研究考拉兹猜想的網頁 
 Collatz Conjecture的BOINC專案網頁 

 An ongoing volunteer computing project  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).

 .




 Are computers ready to solve this notoriously unwieldy math problem? 

Category:数论
Category:猜想
Category:整数数列