茶年 · 中文维基百科

考拉兹猜想

Wikipedia · 2026-06-18 维基百科 👁 1 阅读

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

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

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

问题表述
对任意正整数进行以下运算；

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

这可以定义为模算术函数：
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}

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

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

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

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

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

只要是奇数，就是偶数，所以可以使用考拉兹函数的“快捷”形式：
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}
这个定义可在过程整体动态不变的前提下，获得较小的停止时间和总停止时间值。

经验数据
取一个正整数：

  • 如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個步驟）

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

數目少於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步；……

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

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

可视化
File:Collatz orbits of the all integers up to 1000.svg|前1000个数的轨迹的有向图
File:CollatzConjectureGraphMaxValues.jpg|轴表示初始数，轴表示到1过程中到达的最大值。此图显示了压缩的轴：有些值产生的轨迹最大值可达（）
File:Collatz-max.png|与左图相同，但采用对数坐标，显示了所有值。图中间的第一条粗线对应27处的尖端，在9232到达最大值
File:All Collatz sequences of a length inferior to 20.svg|小于20步的所有数集合
File:Collatz Conjecture 100M.jpg|alt=Collatz Conjecture 100M|前1亿个数到达1的迭代次数

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

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

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

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

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

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

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

循环
在这一节中，考虑考拉兹函数的快捷形式
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}
循环是由不同正整数组成的序列，其中, , ..., 。

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

周期长度
非平凡周期的长度至少为。若能证明对所有小于3 \times 2^{69}的正整数，考拉兹序列都收敛到1，则这个下界就会提高到。Simons (2005)用Steiner的方法证明没有2循环。Simons & de Weger (2005)将这一证明推广到68循环，即以下不存在循环。因此，的表示包含了除的重复尾数，每个重复尾数可以选择旋转，再复制到有限位数。只有二进制会出现这种情况。根据猜想，每个以“1”结尾的二进制字符串都可用这种形式表示（可以添加或删除的前导0）。

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

在二进制数的（右）端加（得到）；

用二进制加法将其加到原数上（）；

去掉所有尾数（反复除以2直到结果为奇数）。

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

111
1111
10110
10111
100010
100011
110100
11011
101000
1011
10000

作为奇偶序列
本节中，考虑略微修改的考拉兹函数
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}.

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

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

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

利用的这种形式，可证明两个数、的奇偶性序列在前项上一致，当且仅当、是等价的模。这意味着每个数都能通过奇偶性序列唯一识别，此外若存在多个考拉兹循环，则它们对应的奇偶性循环也一定是不同的。相反，有人猜想，每个奇分母有理数都有最终循环的奇偶性序列（周期性猜想，可得考拉兹函数
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进数推广
函数
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进整环\mathbb{Z}_2上有精确定义，是连续的，且关于2进度量是保测的。另外，已知其动态是遍历的。因此，每个无限奇偶性序列都恰好出现一恶搞2进整数，所以几乎所有轨迹在\mathbb{Z}_2中都是非循环的。

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

在实数、复数上的迭代
。运用了推广到实数的考拉兹映射。]]

x为整偶数时x/2、为整奇数时3x + 1或(3x + 1)/2（“快捷”版本）的函数，可将考拉兹映射推广到实數，这就是所谓的插值函数。一个简单方法是选取两个函数g_1、g_2，其中
:g_1(n) = \begin{cases}1, &n\text{ is even,}\\ 0, &n\text{ is odd,}\end{cases}
:g_2(n) = \begin{cases}0, &n\text{ is even,}\\1, &n\text{ is odd,}\end{cases}
并将它们作为我们所需值的开关：
: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(\tfrac{\pi}{2} x\right)、g_2(x) \triangleq \sin^2\left(\tfrac{\pi}{2} x\right)。这映射的迭代产生了动力系统，Marc Chamberland对其进行了进一步研究。他证明这个猜想对于正实数不成立，因为存在无穷多个不动点与无穷多单调发散到无穷的轨道。函数f有2个周期为2的吸引子循环：(1;\,2)、(1.1925...;\,2.1386...)。此外，我们猜想无界轨道集的勒贝格测度为0。

Letherman、Schleicher和Wood将研究推广到复平面，用张伯伦函数求解复正余弦，并添加了额外项\tfrac{1}{\pi}\left(\tfrac12 - \cos(\pi z)\right)\sin(\pi z)\,+
h(z)\sin^2(\pi z)，其中h(z)是任意整函数。由于该式对整实数求值为零，所以推广函数
:\begin{align}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(\frac12 - \cos(\pi z)\right)\sin(\pi z) + h(z)\sin^2(\pi z)\end{align}

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

，实部为-5到5。]]

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

还有许多方法可以定义复插值函数，如用复指数而非正余弦：
:f(z) \triangleq \frac{z}{2} + \frac14(2z + 1)\left(1 - e^{i\pi z}\right),
它呈现出不同的动态。例如若\operatorname{Im}(z) \gg 1，则f(z) \approx z + \tfrac14。对应的朱利亚集（如右图）由不可数多的曲线组成，称为“毛”或“线”。

优化
时空权衡
#作为奇偶序列一节给出了加快序列模拟的方法。要在每次迭代中向前跳转步，可将当前数字分成两部分：（个最小有效位，解释为整数）和（剩余位，解释为整数）。向前跳转步的算法是
:.
（或更好的）、的值可针对所有可能的位数预先计算，其中是对应用次函数的结果，是迭代过程中遇到的奇数个数。例如，若，那么每次迭代都可以向前跳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在计算证实考拉兹猜想时，使用了这种加速，直到很大的值。对给定的、，若不等式

:

对所有都成立，那么第一个反例（若存在）不是模。

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

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

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

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

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

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

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

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

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

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

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

相關條目
*3x + 1半群
*模算數
*

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

*

  • An ongoing volunteer computing [https://collatz-problem.org/ project] by David Bařina verifies Convergence of the Collatz conjecture for large values. (furthest progress so far)
  • An ongoing volunteer computing [http://www.ericr.nl/wondrous/index.html project] by Eric Roosendaal verifies the Collatz conjecture for larger and larger values.
  • Another ongoing volunteer computing [http://sweet.ua.pt/tos/3x+1.html 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).

*

  • .

*
*
*
*

#数论 #整数数列 #猜想

评论 (0)

  • 还没有评论，来抢沙发吧。