考拉茲猜想 (英語: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 的迭代下陷入其中:
奇數值用大粗體表示,每個循環以其絕對值最小的成員(總是奇數)為先列出。
More information 循環, 奇數值循環長度 ...
循環
奇數值循環長度
全循環長度
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
Close
推廣的考拉茲猜想:在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 .