考拉兹猜想
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
考拉兹猜想(英语:Collatz conjecture),又称为奇偶归一猜想、3n+1猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想,[1]是指对于每一个正整数,如果它是奇数,则对它乘3再加1,如果它是偶数,则对它除以2,如此循环,最终都能够得到1。
埃尔德什·帕尔在谈到考拉兹猜想时说:“数学还没准备好应对这样的问题。”[2]杰佛瑞·拉加里亚斯指出,考拉兹猜想“是个异常困难的问题,完全超出了当今数学的范围”。[3]
问题表述
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b9/Collatz-stopping-time.svg/220px-Collatz-stopping-time.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/26/CollatzStatistic100million.png/220px-CollatzStatistic100million.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0d/CollatzStatistic1billion.png/220px-CollatzStatistic1billion.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Collatz-10Million.png/220px-Collatz-10Million.png)
![Total Stopping Time: numbers up to 250, 1000, 4000, 20000, 100000, 500000](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Collatz_Gif.gif/220px-Collatz_Gif.gif)
对任意正整数进行以下运算;
- 若为偶数,则除以2;
- 若为奇数,则将其×3再加1。
现重复执行该运算,形成一个序列,从任意正整数开始,把每步的结果作为下一步的输入。可记作: (即:ai是递归i次应用于n的f值;ai = f i(n))。
考拉兹猜想是:所有正整数最终都会到达1,即存在i使得ai = f i(n)= 1。
若猜想为假,表示存在某个初值产生一个不含1的循环数列,或朝无穷大发散的数列,目前尚未发现这样的数列。
最小的使ai < a0 的i称为n的停止时间,相似地,使ak = 1的最小的k称为n的总停止时间。[4]若索引i或k的其中一个不存在,就称停止时间或总停止时间分别不存在。
考拉兹猜想认为,所有n的总停止时间都是有限的,即所有n ≥ 2都有有限的停止时间。
只要n是奇数,3n + 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个步骤)(OEIS数列A008884)
奇偶归一猜想称,任何正整数,经过上述计算步骤后,最终都会得到1。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/96/Collatz5.svg/500px-Collatz5.svg.png)
数目少于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步;
- 小于104的是6171,经历261步;
- 小于105的是031,经历350步; 77
- 小于106的是799,经历524步; 837
- 小于107的是400511,经历685步; 8
- 小于108的是728127,经历949步; 63
- 小于109的是617279,经历986步; 670
- 小于1010的是780657630,经历1132步; 9[5]
- 小于1011的是128138247,经历1228步; 75
- 小于1012的是345275647,经历1348步;…… 989[6] (OEIS数列A284668)
这些数字也是具有指定步数的最低数字,但不一定是唯一的,例如经历1132步的有780657631,还有 9780657630。 9
与位数(以2为基)相关的总停止时间最小的起始值是2的幂,因为2n经历n次减半才达到1,且永远不会增加。
可视化
[编辑]-
前1000个数的轨迹的有向图
-
x轴表示初始数,y轴表示到1过程中到达的最大值。此图显示了压缩的y轴:有些x值产生的轨迹最大值可达×107( 2.7x = 9663)
-
与左图相同,但采用对数坐标,显示了所有y值。图中间的第一条粗线对应27处的尖端,在9232到达最大值
-
小于20步的所有数集合
-
前1亿个数到达1的迭代次数
支持论据
[编辑]虽然猜想尚未得到证实,但大多数数学家都认为它是真的,因为实验证据和启发式论证都支持这一猜想。
实验证据
[编辑]截至2020年,已经用计算机验证了268 ≈ ×1020之前的所有初始值,最终都以周期为3的循环 2.95(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的整数个数至少等于x0.84。[15]
循环
[编辑]在这一节中,考虑考拉兹函数的快捷形式 循环是由不同正整数组成的序列(a0, a1, ..., aq),其中f(a0) = a1, f(a1) = a2, ..., f(aq) = a0。
唯一已知的循环是周期为2的(1,2),称作平凡循环。
周期长度
[编辑]非平凡周期的长度至少为265759595。若能证明对所有小于 186的正整数,考拉兹序列都收敛到1,则这个下界就会提高到504839929。 355[16][9]实际上,Eliahou (1993)证明了任何非平凡循环的周期p的形式为 其中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值。
猜想的其他表述
[编辑]反向
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Collatz-tree%2C_depth%3D20.svg/440px-Collatz-tree%2C_depth%3D20.svg.png)
还有另一种方法可证明这猜想:采用自下而上的方法构造所谓考拉兹图,由逆关系定义:
因此,与其证明所有正整数都指向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代替,则考拉兹图由逆关系定义:
对任意整数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(即fk(n) = 1)。则数字n在二进制中可写为字符串wk wk−1 ... w1,其中每个wh都是从1/3h的表示中提取的有限连续字符串。[19]因此,n的表示包含了除1/3h的重复尾数,每个重复尾数可以选择旋转,再复制到有限位数。只有二进制会出现这种情况。[20]根据猜想,每个以“1”结尾的二进制字符串s都可用这种形式表示(可以添加或删除s的前导0)。
作为以二进制计算的抽象机
[编辑]考拉兹函数的重复应用可用处理比特串的抽象机表示。它会对任何奇数执行以下3步,直到只剩一个1:
- 在二进制数的(右)端加1(得到2n + 1);
- 用二进制加法将其加到原数上(2n + 1 + n = 3n + 1);
- 去掉所有尾数0(反复除以2直到结果为奇数)。
示例
[编辑]起始值为7,以二进制写作111。得到的考拉兹序列为:
111 1111 1011010111 100010100011 11010011011 1010001011 10000
作为奇偶序列
[编辑]本节中,考虑略微修改的考拉兹函数
这样做是因为n为奇数时,3n + 1总是偶数。
若P(...)表示某数的奇偶性,例如P(2n) = 0、P(2n + 1) = 1,则可定义一个数n的考拉兹奇偶序列pi = P(ai),其中a0 = n;ai+1 = f(ai)。
执行3n + 1/2还是n/2的哪种运算取决于奇偶性,序列与运算序列相同。
利用f(n)的这种形式,可证明两个数m、n的奇偶性序列在前k项上一致,当且仅当m、n是等价的模2k。这意味着每个数都能通过奇偶性序列唯一识别,此外若存在多个考拉兹循环,则它们对应的奇偶性循环也一定是不同的。[4][12]
对数n = 2ka + b应用k次f函数,得到3ca + d,其中d是对b应用k次f函数的结果,c是在序列中增加的次数。例如,对于25a + 1,1依次上升到2、1、2、1,最后上升到2时有3次上升,因此结果是33a + 2;对于22a + 1只有一次上升:1、2、1,所以结果是3a + 1。b是2k − 1时,会有k次上升,结果是3ka + 3k − 1。3的幂乘a与a无关,只取决于b的行为,这使我们可以预测,某些形式的数在迭代一定次数后总会到达更小的数字,例如4a + 1在应用两次f后会变成3a + 1,16a + 3应用4次会变成9a + 2。不过,这些小数是否继续下降到1则取决于a的值。
作为标记系统
[编辑]对于形式为
的考拉兹函数,考拉兹序列可通过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,且在k0 < ⋯ < km−1处包含了m次奇数,那么立即周期性地产生奇偶循环的唯一有理数:
例如,奇偶循环(1 0 1 1 0 0 1)长度为7,4个奇数项分别位于0、2、3、6处。它由分数 因为后者可产生有理循环
(1 0 1 1 0 0 1)的任何循环排列都与上述分数之一相关。例如,循环(0 1 1 0 0 1 1)可由下面的分数产生
为实现一一对应,奇偶循环应是不可还原的,即无法分割成相同的子循环。例如,奇偶循环(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],可得考拉兹函数
2进数推广
[编辑]函数 在2进整环上有精确定义,是连续的,且关于2进度量是保测的。另外,已知其动态是遍历的。[4]
定义作用于的奇偶矢量函数Q:
函数Q是2进等距同构。[23]因此,每个无限奇偶性序列都恰好出现一恶搞2进整数,所以几乎所有轨迹在中都是非循环的。
考拉兹猜想的等价表述是
在实数、复数上的迭代
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Collatz_Cobweb.svg/220px-Collatz_Cobweb.svg.png)
为整偶数时、为整奇数时或(“快捷”版本)的函数,可将考拉兹映射推广到实线,这就是所谓的插值函数。一个简单方法是选取两个函数、,其中
并将它们作为我们所需值的开关:
- .
其中一个选择是、。这映射的迭代产生了动力系统,Marc Chamberland对其进行了进一步研究。[24]他证明这个猜想对于正实数不成立,因为存在无穷多个不动点与无穷多单调发散到无穷的轨道。函数有2个周期为的吸引子循环:、。此外,我们猜想无界轨道集的勒贝格测度为。
Letherman、Schleicher和Wood将研究推广到复平面,[25]用张伯伦函数求解复正余弦,并添加了额外项 ,其中是任意整函数。由于该式对整实数求值为零,所以推广函数
是考拉兹映射到复平面的插值。添加额外项将所有整数都变为的临界点,于是可证明没有一个整数位于Baker域中,意味着任何整数或者是周期性的,或者属于游荡域。他们猜想后者不成立,也就可以导出,所有整数轨都是有限的。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8c/Collatz_Fractal.jpg/220px-Collatz_Fractal.jpg)
大部分点的轨道发散,根据发散速度为其着色,便产生左边的图像()。内部黑色区域和外部是法图元素,之间的边界是的朱利亚集,有时称为“考拉兹分形”。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/74/Exponential_Collatz_Fractal.jpg/220px-Exponential_Collatz_Fractal.jpg)
还有许多方法可以定义复插值函数,如用复指数而非正余弦:
- ,
它呈现出不同的动态。例如若,则。对应的朱利亚集(如右图)由不可数多的曲线组成,称为“毛”或“线”。
优化
[编辑]时空权衡
[编辑]#作为奇偶序列一节给出了加快序列模拟的方法。要在每次迭代中向前跳转k步,可将当前数字分成两部分:b(k个最小有效位,解释为整数)和a(剩余位,解释为整数)。向前跳转k步的算法是
- fk(2ka + b) = 3c(b, k)a + d(b, k).
c(或更好的3c)、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 }.
这需要2k的预计算和存储,以将计算速度提高k倍,是时空权衡。
模限制
[编辑]对于寻找考拉兹猜想反例,这种预计算带来了更重要的加速。Tomás Oliveira e Silva在计算证实考拉兹猜想时,使用了这种加速,直到很大的n值。对给定的b、k,若不等式
- f'k(2ka + b) = 3c(b)a + d(b) < 2ka + b
对所有a都成立,那么第一个反例(若存在)不是b模2k。[27]例如,第一个反例一定是奇数,因为f(2n) = n小于2n;且一定是3 mod 4,因为f2(4n + 1) = 3n + 1,小于4n + 1。对每个不是考拉兹猜想反例的初值a,都存在使不等式成立的k,因此检查起始值的考拉兹猜想,相当于检查整个同余类。随着k增加,只需搜索没有被较小的k消除的残差b,将只剩极少数。[4]例如,32模的残差只有7、15、27、31。
锡拉丘兹函数
[编辑]若k为奇整数,则3k + 1是偶数,所以3k + 1 = 2ak′,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,fp − 1(2ph − 1) = 2 × 3p − 1h − 1。(其中fp − 1是函数迭代记号。)
- 对所有奇数h,f(2h − 1) ≤ 3h − 1/2
考拉兹猜想等价于:对l中所有k,存在整数n ≥ 1使fn(k) = 1。
不可判定的推广
[编辑]1972年,约翰·康威证明了考拉兹猜想的一个自然推广在算法上是不可判定的。[28]
具体来说,他考虑了以下形式的函数 其中a0, b0, ..., aP − 1, bP − 1是有理数,其选择使g(n)总是整数。标准考拉兹函数为P = 2、a0 = 1/2、b0 = 0, a1 = 3、b1 = 1。康威证明
- 给定g、n,迭代序列gk(n)是否能抵达1?
是不可判定的,可以转化为停机问题。
与考拉兹猜想更接近的是下面这个普遍量化问题:
- 给定g,迭代序列gk(n)对所有n > 0是否都能抵达1?
以这种方式修改条件,可以使问题变得更难或更易解决(直观地说,正面答案更难证明,但反面答案可能更容易)。Kurtz & Simon[29]证明,普遍量化问题事实上是不可判定的,在算术阶层中甚至更高;具体地说,它是Π0
2完全的。即使将模数P限制在6840以限制函数g的类别,这难度结果也成立。[30]
这种形式的简化迭代(所有都为零)在一种名为FFRACTRAN的编程语言中得到了正式化。
研究历史
[编辑]在1930年代,德国汉堡大学的学生洛萨·考拉兹曾经研究过这个猜想。在1960年,角谷静夫也研究过这个猜想。但这猜想到目前,仍没有任何进展。
保罗·艾狄胥就曾称,数学上尚未为此类问题提供答案。他并称会替找出答案的人奖赏500元。
目前已经有分布式计算在进行验证。到2020年,已验证正整数到,也仍未有找到例外的情况。但是这并不能够证明对于任何大小的数,这猜想都能成立。
有的数学家认为,该猜想任何程度的解决都是现代数学的一大进步,将开辟全新的领域。目前也有部分数学家和数学爱好者,在进行关于“负数的”、“”、“”等种种考拉兹猜想的变化形命题的研究。
2019年12月,陶哲轩证明只要是一个趋于正无穷的实数列,那么几乎对所有的正整数(在对数密度意义下) ,有。[31][32]
相关条目
[编辑]阅读更多
[编辑]参考资料
[编辑]- ^ 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.
- ^ 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.0 3.1 Lagarias, Jeffrey C. (编). The Ultimate Challenge: The 3x + 1 Problem. American Mathematical Society. 2010. ISBN 978-0-8218-4940-8. Zbl 1253.11003.
- ^ 4.0 4.1 4.2 4.3 4.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.
- ^ 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
.
- ^ Roosendaal, Eric. 3x+1 delay records. [2020-03-14]. (原始内容存档于2023-03-27). (Note: "Delay records" are total stopping time records.)
- ^ 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.
- ^ 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.0 9.1 9.2 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.0 10.1 10.2 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).
- ^ Lagarias (1985) section "A heuristic argument".
- ^ 12.0 12.1 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).
- ^ 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
(英语).
- ^ Hartnett, Kevin. Mathematician Proves Huge Result on ‘Dangerous’ Problem. Quanta Magazine. 2019-12-11 [2023-11-12]. (原始内容存档于2024-01-16).
- ^ 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.0 16.1 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).
- ^ Steiner, R. P. A theorem on the syracuse problem. Proceedings of the 7th Manitoba Conference on Numerical Mathematics. 1977: 553–9. MR 0535032.
- ^ 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
.
- ^ 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
.
- ^ Hew, Patrick Chisan. Working in binary protects the repetends of 1/3h: 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
.
- ^ 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).
- ^ 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).
- ^ 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
(英语).
- ^ Chamberland, Marc. A continuous extension of the 3x + 1 problem to the real line. Dynam. Contin. Discrete Impuls Systems. 1996, 2 (4): 495–509.
- ^ 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.
- ^ 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).
- ^ 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
.
- ^ Conway, John H. Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder: 49–52. 1972.
- ^ 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
- ^ 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.
- ^ Kevin Hartnett. Mathematician Proves Huge Result on ‘Dangerous’ Problem. Quantamagazine. 2019-12-11 [2019-12-16]. (原始内容存档于2020-06-18).
- ^ 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? (页面存档备份,存于互联网档案馆)