考拉兹猜想 (英語:Collatz conjecture ),又称为奇偶归一猜想 、3n+1猜想 、冰雹猜想 、角谷猜想 、哈塞猜想 、乌拉姆猜想 或叙拉古猜想 ,[ 1] 是指对于每一个正整数 ,如果它是奇数 ,则对它乘3再加1,如果它是偶数 ,则对它除以2 ,如此循环,最终都能够得到1。
f
(
n
)
=
{
n
/
2
if
n
≡
0
3
n
+
1
if
n
≡
1
(
mod
2
)
.
{\displaystyle 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到9999的数字及其相应的停止时间
1到108 的总停止时间直方图,x轴为总停止时间,y轴为频率。
1到109 的总停止时间柱状图直方图,x轴为总停止时间,y轴为频率。
2到107 的迭代时间
总停止时间:最高250、1000、4000、20000、100000、500000的数字
对任意正整数 进行以下运算;
若为偶数,则除以2;
若为奇数,则将其×3再加1。
这可以定义为模算术 函数 f :
f
(
n
)
=
{
n
/
2
if
n
≡
0
(
mod
2
)
,
3
n
+
1
if
n
≡
1
(
mod
2
)
.
{\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}}}
现重复执行该运算,形成一个序列,从任意正整数开始,把每步的结果作为下一步的输入。可记作:
a
i
=
{
n
for
i
=
0
,
f
(
a
i
−
1
)
for
i
>
0
{\displaystyle a_{i}={\begin{cases}n&{\text{for }}i=0,\\f(a_{i-1})&{\text{for }}i>0\end{cases}}}
(即:ai 是递归i 次应用于n 的f 值;ai = f i (n ) )。
考拉兹猜想是:所有正整数最终都会到达1,即存在i使得ai = f i (n )= 1 。
若猜想为假,表示存在某个初值产生一个不含1的循环数列,或朝無窮大發散的數列,目前尚未发现这样的数列。
最小的使ai < a 0 的i 称为n 的停止时间 ,相似地,使ak = 1 的最小的k 称为n 的总停止时间 。[ 4] 若索引i 或k 的其中一个不存在,就称停止时间或总停止时间分别不存在。
考拉兹猜想认为,所有n 的总停止时间都是有限的,即所有n ≥ 2 都有有限的停止时间。
只要n 是奇数,3n + 1 就是偶数,所以可以使用考拉兹函数的“快捷”形式:
f
(
n
)
=
{
n
2
if
n
≡
0
(
mod
2
)
,
3
n
+
1
2
if
n
≡
1
(
mod
2
)
.
{\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}}}
这个定义可在过程整体动态不变的前提下,获得较小的停止时间和总停止时间值。
取一个正整数:
如
n
{\displaystyle n}
= 6,根据上述数式,得出序列6, 3, 10, 5, 16 , 8, 4, 2, 1。(步驟中最高的數是16,共有8個步驟)
如
n
{\displaystyle n}
= 11,根据上述数式,得出序列11, 34, 17, 52 , 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。(步驟中最高的數是52,共有14個步驟)
如
n
{\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。
n
{\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步;
小于104 的是6171,经历261步;
小于105 的是7004770310000000000♠ 77031 ,经历350步;
小于106 的是7005837799000000000♠ 837799 ,经历524步;
小于107 的是7006840051100000000♠ 8400 511 ,经历685步;
小于108 的是7007637281270000000♠ 63728 127 ,经历949步;
小于109 的是7008670617279000000♠ 670617 279 ,经历986步;
小于1010 的是7009978065763000000♠ 9780 657 630 ,经历1132步;[ 5]
小于1011 的是7010751281382470000♠ 75128 138 247 ,经历1228步;
小于1012 的是7011989345275647000♠ 989345 275 647 ,经历1348步;……[ 6] (OEIS 數列A284668 )
这些数字也是具有指定步数的最低数字,但不一定是唯一的,例如经历1132步的有7009978065763100000♠ 9780 657 631 ,还有7009978065763000000♠ 9780 657 630 。
与位数(以2为基)相关的总停止时间最小的起始值是2的幂,因为2n 经历n 次减半才达到1,且永远不会增加。
虽然猜想尚未得到证实,但大多数数学家都认为它是真的,因为实验证据和启发式论证都支持这一猜想。
截至2020年,已经用计算机验证了268 ≈ 7020295000000000000♠ 2.95× 1020 之前的所有初始值,最终都以周期为3的循环(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的整数个数至少等于x 0.84 。[ 15]
在这一节中,考虑考拉兹函数的快捷形式
f
(
n
)
=
{
n
2
if
n
≡
0
(
mod
2
)
,
3
n
+
1
2
if
n
≡
1
(
mod
2
)
.
{\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 0 , a 1 , ..., aq ) ,其中f (a 0 ) = a 1 , f (a 1 ) = a 2 , ..., f (aq ) = a 0 。
唯一已知的循环是周期为2的(1,2) ,称作平凡循环。
非平凡周期的长度至少为7011186265759595000♠ 186265 759 595 。若能证明对所有小于
3
×
2
69
{\displaystyle 3\times 2^{69}}
的正整数,考拉兹序列都收敛到1,则这个下界就会提高到7011355504839929000♠ 355504 839 929 。[ 16] [ 9] 实际上,Eliahou (1993)证明了任何非平凡循环的周期p 的形式为
p
=
301994
a
+
17087915
b
+
85137581
c
{\displaystyle p=301994a+17087915b+85137581c}
其中a 、b 、c 为非负整数,b ≥ 1 ,ac = 0 。这个结果是基于ln 3 / ln 2 的连分数 展开。[ 9]
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的数字
还有另一种方法可证明这猜想:采用自下而上的方法构造所谓考拉兹图 ,由逆关系 定义:
R
(
n
)
=
{
{
2
n
}
if
n
≡
0
,
1
,
2
,
3
,
5
{
2
n
,
n
−
1
3
}
if
n
≡
4
(
mod
6
)
.
{\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 代替,则考拉兹图由逆关系定义:
R
(
n
)
=
{
{
2
n
}
if
n
≡
0
,
1
{
2
n
,
2
n
−
1
3
}
if
n
≡
2
(
mod
3
)
.
{\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 1 ,其中每个w h 都是从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
10110
10111
100010
100011
110100
11011
101000
1011
10000
本节中,考虑略微修改的考拉兹函数
f
(
n
)
=
{
n
2
if
n
≡
0
3
n
+
1
2
if
n
≡
1
(
mod
2
)
.
{\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 的考拉兹奇偶序列pi = P(ai ) ,其中a 0 = n ;a i +1 = f (a i ) 。
执行3n + 1 / 2 还是n / 2 的哪种运算取决于奇偶性,序列与运算序列相同。
利用f (n ) 的这种形式,可证明两个数m 、n 的奇偶性序列在前k 项上一致,当且仅当m 、n 是等价的模2k 。这意味着每个数都能通过奇偶性序列唯一识别,此外若存在多个考拉兹循环,则它们对应的奇偶性循环也一定是不同的。[ 4] [ 12]
对数n = 2k a + b 应用k 次f 函数,得到3c a + d ,其中d 是对b 应用k 次f 函数的结果,c 是在序列中增加的次数。例如,对于25 a + 1 ,1依次上升到2、1、2、1,最后上升到2时有3次上升,因此结果是33 a + 2 ;对于22 a + 1 只有一次上升:1、2、1,所以结果是3a + 1 。b 是2k − 1 时,会有k 次上升,结果是3k a + 3k − 1 。3的幂乘a 与a 无关,只取决于b 的行为,这使我们可以预测,某些形式的数在迭代一定次数后总会到达更小的数字,例如4a + 1 在应用两次f 后会变成3a + 1 ,16a + 3 应用4次会变成9a + 2 。不过,这些小数是否继续下降到1则取决于a 的值。
对于形式为
f
(
n
)
=
{
n
2
if
n
≡
0
3
n
+
1
2
if
n
≡
1.
(
mod
2
)
{\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 0 < ⋯ < k m −1 处包含了m 次奇数,那么立即周期性地产生奇偶循环的唯一有理数:
3
m
−
1
2
k
0
+
⋯
+
3
0
2
k
m
−
1
2
n
−
3
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处。它由分数
3
3
2
0
+
3
2
2
2
+
3
1
2
3
+
3
0
2
6
2
7
−
3
4
=
151
47
{\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}}}
因为后者可产生有理循环
151
47
→
250
47
→
125
47
→
211
47
→
340
47
→
170
47
→
85
47
→
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) 可由下面的分数产生
3
3
2
1
+
3
2
2
2
+
3
1
2
5
+
3
0
2
6
2
7
−
3
4
=
250
47
.
{\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] ,可得考拉兹函数
T
d
(
x
)
=
{
x
2
if
x
≡
0
(
mod
2
)
,
3
x
+
d
2
if
x
≡
1
(
mod
2
)
.
{\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}}}
函数
T
(
x
)
=
{
x
2
if
x
≡
0
(
mod
2
)
3
x
+
1
2
if
x
≡
1
(
mod
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进整环
Z
2
{\displaystyle \mathbb {Z} _{2}}
上有精确定义,是连续的,且关于2进度量是保测的。另外,已知其动态是遍历 的。[ 4]
定义作用于
Z
2
{\displaystyle \mathbb {Z} _{2}}
的奇偶矢量函数Q :
Q
(
x
)
=
∑
k
=
0
∞
(
T
k
(
x
)
mod
2
)
2
k
.
{\displaystyle Q(x)=\sum _{k=0}^{\infty }\left(T^{k}(x)\mod 2\right)2^{k}.}
函数Q 是2进等距同构 。[ 23] 因此,每个无限奇偶性序列都恰好出现一恶搞2进整数,所以几乎所有 轨迹在
Z
2
{\displaystyle \mathbb {Z} _{2}}
中都是非循环的。
考拉兹猜想的等价表述是
Q
(
Z
+
)
⊂
1
3
Z
.
{\displaystyle Q\left(\mathbb {Z} ^{+}\right)\subset {\tfrac {1}{3}}\mathbb {Z} .}
10 → 5 → 8 → 4 → 2 → 1 → ..迭代轨迹的蜘蛛图 。运用了推广到实数的考拉兹映射。
x
{\displaystyle x}
为整偶数时
x
/
2
{\displaystyle x/2}
、为整奇数时
3
x
+
1
{\displaystyle 3x+1}
或
(
3
x
+
1
)
/
2
{\displaystyle (3x+1)/2}
(“快捷”版本)的函数,可将考拉兹映射推广到实數 ,这就是所谓的插值 函数。一个简单方法是选取两个函数
g
1
{\displaystyle g_{1}}
、
g
2
{\displaystyle g_{2}}
,其中
g
1
(
n
)
=
{
1
,
n
is even,
0
,
n
is odd,
{\displaystyle g_{1}(n)={\begin{cases}1,&n{\text{ is even,}}\\0,&n{\text{ is odd,}}\end{cases}}}
g
2
(
n
)
=
{
0
,
n
is even,
1
,
n
is odd,
{\displaystyle g_{2}(n)={\begin{cases}0,&n{\text{ is even,}}\\1,&n{\text{ is odd,}}\end{cases}}}
并将它们作为我们所需值的开关:
f
(
x
)
≜
x
2
⋅
g
1
(
x
)
+
3
x
+
1
2
⋅
g
2
(
x
)
{\displaystyle f(x)\triangleq {\frac {x}{2}}\cdot g_{1}(x)\,+\,{\frac {3x+1}{2}}\cdot g_{2}(x)}
.
其中一个选择是
g
1
(
x
)
≜
cos
2
(
π
2
x
)
{\displaystyle g_{1}(x)\triangleq \cos ^{2}\left({\tfrac {\pi }{2}}x\right)}
、
g
2
(
x
)
≜
sin
2
(
π
2
x
)
{\displaystyle g_{2}(x)\triangleq \sin ^{2}\left({\tfrac {\pi }{2}}x\right)}
。这映射的迭代 产生了动力系统 ,Marc Chamberland对其进行了进一步研究。[ 24] 他证明这个猜想对于正实数不成立,因为存在无穷多个不动点 与无穷多单调 发散到无穷的轨道。函数
f
{\displaystyle f}
有2个周期为
2
{\displaystyle 2}
的吸引子 循环:
(
1
;
2
)
{\displaystyle (1;\,2)}
、
(
1.1925...
;
2.1386...
)
{\displaystyle (1.1925...;\,2.1386...)}
。此外,我们猜想无界轨道集的勒贝格测度 为
0
{\displaystyle 0}
。
Letherman、Schleicher和Wood将研究推广到复平面 ,[ 25] 用张伯伦函数求解复正余弦,并添加了额外项
1
π
(
1
2
−
cos
(
π
z
)
)
sin
(
π
z
)
+
{\displaystyle {\tfrac {1}{\pi }}\left({\tfrac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)\,+}
h
(
z
)
sin
2
(
π
z
)
{\displaystyle h(z)\sin ^{2}(\pi z)}
,其中
h
(
z
)
{\displaystyle h(z)}
是任意整函数 。由于该式对整实数求值为零,所以推广函数
f
(
z
)
≜
z
2
cos
2
(
π
2
z
)
+
3
z
+
1
2
sin
2
(
π
2
z
)
+
1
π
(
1
2
−
cos
(
π
z
)
)
sin
(
π
z
)
+
h
(
z
)
sin
2
(
π
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}}}
是考拉兹映射到复平面的插值。添加额外项将所有整数都变为
f
{\displaystyle f}
的临界点 ,于是可证明没有一个整数位于Baker域中,意味着任何整数或者是周期性的,或者属于游荡域 。他们猜想后者不成立,也就可以导出,所有整数轨都是有限的。
以原点为中心的考拉兹分形 ,实部为-5到5。
大部分点的轨道发散,根据发散速度为其着色,便产生左边的图像(
h
(
z
)
≜
0
{\displaystyle h(z)\triangleq 0}
)。内部黑色区域和外部是法图元素,之间的边界是
f
{\displaystyle f}
的朱利亚集 ,有时称为“考拉兹分形 ”。
指数插值的朱利亚集
还有许多方法可以定义复插值函数,如用复指数而非正余弦:
f
(
z
)
≜
z
2
+
1
4
(
2
z
+
1
)
(
1
−
e
i
π
z
)
{\displaystyle f(z)\triangleq {\frac {z}{2}}+{\frac {1}{4}}(2z+1)\left(1-e^{i\pi z}\right)}
,
它呈现出不同的动态。例如若
Im
(
z
)
≫
1
{\displaystyle \operatorname {Im} (z)\gg 1}
,则
f
(
z
)
≈
z
+
1
4
{\displaystyle f(z)\approx z+{\tfrac {1}{4}}}
。对应的朱利亚集(如右图)由不可数多的曲线组成,称为“毛”或“线”。
#作为奇偶序列 一节给出了加快序列模拟的方法。要在每次迭代中向前跳转k 步,可将当前数字分成两部分:b (k 个最小有效位,解释为整数)和a (剩余位,解释为整数)。向前跳转k 步的算法是
f k (2k a + 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 (2k a + b ) = 3c (b )a + d (b ) < 2k a + b
对所有a 都成立,那么第一个反例(若存在)不是b 模2k 。[ 27] 例如,第一个反例一定是奇数,因为f (2n ) = n 小于2n ;且一定是3 mod 4,因为f 2 (4n + 1) = 3n + 1 ,小于4n + 1 。对每个不是考拉兹猜想反例的初值a ,都存在使不等式成立的k ,因此检查起始值的考拉兹猜想,相当于检查整个同余类。随着k 增加,只需搜索没有被较小的k 消除的残差b ,将只剩极少数。[ 4] 例如,32模的残差只有7、15、27、31。
若k 为奇整数,则3k + 1 是偶数,所以3k + 1 = 2a k ′ ,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 (2p h − 1) = 2 × 3p − 1h − 1 。(其中f p − 1 是函数迭代记号 。)
对所有奇数h ,f (2h − 1) ≤ 3h − 1 / 2
考拉兹猜想等价于:对l 中所有k ,存在整数n ≥ 1 使f n (k ) = 1 。
主条目:FRACTRAN
1972年,约翰·康威 证明了考拉兹猜想的一个自然推广在算法上是不可判定的 。[ 28]
具体来说,他考虑了以下形式的函数
g
(
n
)
=
a
i
n
+
b
i
when
n
≡
i
(
mod
P
)
,
{\displaystyle {g(n)=a_{i}n+b_{i}}{\text{ when }}{n\equiv i{\pmod {P}}},}
其中a 0 , b 0 , ..., a P − 1 , b P − 1 是有理数,其选择使g (n ) 总是整数。标准考拉兹函数为P = 2 、a 0 = 1 / 2 、b 0 = 0 , a 1 = 3 、b 1 = 1 。康威证明
给定g 、n ,迭代序列gk (n ) 是否能抵达1 ?
是不可判定的,可以转化为停机问题 。
与考拉兹猜想更接近的是下面这个普遍量化问题:
给定g ,迭代序列gk (n ) 对所有n > 0 是否都能抵达1 ?
以这种方式修改条件,可以使问题变得更难或更易解决(直观地说,正面答案更难证明,但反面答案可能更容易)。Kurtz & Simon[ 29] 证明,普遍量化问题事实上是不可判定的,在算术阶层 中甚至更高;具体地说,它是Π0 2 完全的。即使将模数P 限制在6840以限制函数g 的类别,这难度结果也成立。[ 30]
这种形式的简化迭代(所有
b
i
{\displaystyle b_{i}}
都为零)在一种名为FFRACTRAN 的编程语言中得到了正式化。
在1930年代,德国 汉堡大学 的学生洛薩·考拉兹 曾经研究过这个猜想。在1960年,角谷静夫 也研究过这个猜想。但这猜想到目前,仍没有任何进展。
保羅·艾狄胥 就曾称,数学上尚未为此类问题提供答案。他并称会替找出答案的人奖赏500元。
目前已经有分布式计算 在进行验证。到2020年,已验证正整数 到
2
68
{\displaystyle 2^{68}}
,也仍未有找到例外的情况。但是这并不能够证明对於任何大小的数,这猜想都能成立。
有的数学家认为,该猜想任何程度的解决都是现代数学的一大进步,将开辟全新的领域。目前也有部分数学家和数学爱好者,在进行关于“负数的
3
x
+
1
{\displaystyle 3x+1}
”、“
5
x
+
1
{\displaystyle 5x+1}
”、“
7
x
+
1
{\displaystyle 7x+1}
”等種種考拉兹猜想的變化形命題的研究。
2019年12月,陶哲轩 证明只要
f
(
n
)
{\displaystyle f(n)}
是一个趋于正无穷的实数列,那么几乎对所有的正整数
n
{\displaystyle n}
(在对数密度 意义下) ,有
S
(
n
)
<
f
(
n
)
{\displaystyle S(n)<f(n)}
。[ 31] [ 32]
The Ultimate Challenge: The 3x + 1 Problem ,[ 3] 由美国数学学会 于2010年出版,Jeffrey Lagarias编辑,是关于考拉兹猜想、处理方法和一般化思想的资料汇编。其中包含两篇编者所撰的调查论文和5篇与其他作者撰写的论文,内容涉及问题的历史、一般化、统计方法与计算理论 的结果。它还包含有关主题的早期论文的重印本,如洛萨·考拉兹的论文。
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.
Roosendaal, Eric. 3x+1 delay records . [2020-03-14 ] . (原始内容存档 于2023-03-27). (Note: "Delay records" are total stopping time records.)
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 .
Steiner, R. P. A theorem on the syracuse problem. Proceedings of the 7th Manitoba Conference on Numerical Mathematics. 1977: 553–9. MR 0535032 .
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 .
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 .
Conway, John H. Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder: 49–52. 1972.
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 .