考拉茲猜想
![本頁使用了標題或全文手工轉換](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? (頁面存檔備份,存於互聯網檔案館)