由 L. 科拉茨於 1937 年提出的問題,也稱為 對映、
問題、哈塞演算法、角谷猜想、錫拉丘茲演算法、錫拉丘茲問題、Thwaites 猜想和烏拉姆問題 (Lagarias 1985)。Thwaites (1996) 為解決該猜想提供了 1000 英鎊的獎勵。設
為一個整數。那麼,科拉茨猜想的一種形式是詢問迭代
|
(1)
|
對於正數 是否總是返回到 1。(如果包括負數,則有四個已知的迴圈(不包括平凡的 0 迴圈):(4, 2, 1)、(
,
)、(
,
,
,
,
) 和 (
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
)。)
由序列產生的科拉茨猜想的成員有時被稱為冰雹數。Conway 證明了原始的科拉茨猜想沒有長度小於 的非平凡迴圈。Lagarias (1985) 表明,沒有長度小於
的非平凡迴圈。Conway (1972) 還證明了科拉茨型別的猜想在形式上可能是不可判定的。Kurtz 和 Simon (2007) 證明了科拉茨猜想的自然推廣是不可判定的;不幸的是,這個證明不能應用於原始的科拉茨猜想。
科拉茨演算法已經過測試,發現對於所有小於等於 (約 5.48×10^(18))的數字,總是能達到 1 (Oliveira e Silva 2008),改進了早期的
(Vardi 1991, p. 129) 和
(Leavens and Vermeulen 1992) 的結果。由於解決這個問題非常困難,Erdős 評論說“數學尚未為解決此類問題做好準備” (Lagarias 1985)。
下表給出了前幾個起始值獲得的序列 (OEIS A070165)。
| 1 | 1 |
| 2 | 2, 1 |
| 3 | 3, 10, 5, 16, 8, 4, 2, 1 |
| 4 | 4, 2, 1 |
| 5 | 5, 16, 8, 4, 2, 1 |
| 6 | 6, 3, 10, 5, 16, 8, 4, 2, 1 |
演算法達到 1 所需的步數,對於 , 2, ... 分別是 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, ... (OEIS A006577;如上圖所示)。其中,三倍步數是 0, 0, 2, 0, 1, 2, 5, 0, 6, ... (OEIS A006667),而減半步數是 0, 1, 5, 2, 4, 6, 11, 3, 13, ... (OEIS A006666)。產生包含
, 2, ... 的科拉茨序列的最小起始值
分別是 1, 2, 3, 3, 3, 6, 7, 3, 9, 3, 7, 12, 7, 9, 15, 3, 7, 18, 19, ... (OEIS A070167)。
科拉茨猜想可以用 8-暫存器機器 (Wolfram 2002, p. 100)、準細胞自動機 (Cloney et al. 1987, Bruschi 2005) 或 6 色一維準細胞自動機來實現,後者具有區域性規則,但會環繞首尾數字 (Zeleny)。一般來說,構建真正的區域性規則細胞自動機的困難在於乘以 3 時需要進位操作,在最壞的情況下,進位操作可能會擴充套件到基數- 位表示的整個長度(因此需要以快於 CA 光速的速度傳播資訊)。
科拉茨猜想被 Terras (1976, 1979) 修改,他詢問迭代
|
(2)
|
對於初始整數值 是否總是返回到 1(例如,Lagarias 1985, Cloney et al. 1987)。這只是上面的原始陳述,但如果
是奇數,則將除以 2 的步驟合併到加法步驟中,從而壓縮了步數。下表給出了前幾個起始值
, 2, ... 的序列 (OEIS A070168)。
| 1 | 1 |
| 2 | 2, 1 |
| 3 | 3, 5, 8, 4, 2, 1 |
| 4 | 4, 2, 1 |
| 5 | 5, 8, 4, 2, 1 |
| 6 | 6, 3, 5, 8, 4, 2, 1 |
| 7 | 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1 |
如果包括負數,則有 4 個已知的迴圈:(1, 2)、()、(
,
,
) 和 (
,
,
,
,
,
,
,
,
,
,
)。它是“廣義科拉茨猜想”的一個特例,其中
,
,
,
和
。Terras (1976, 1979) 還證明了整數集
具有極限漸近密度
,這樣,如果
是滿足
且
和
的 n 的數量,則極限
|
(3)
|
存在。此外,當 時,
,因此幾乎所有整數都具有有限的停止時間。最後,對於所有
,
|
(4)
|
其中
|
(5)
| |||
|
(6)
| |||
|
(7)
|
(Lagarias 1985)。
科拉茨猜想的推廣讓 為正整數,
, ...,
為非零整數。還讓
滿足
|
(8)
|
然後
|
(9)
|
對於 定義了一個廣義科拉茨對映。一個等價的形式是
|
(10)
|
對於 ,其中
, ...,
是整數,
是向下取整函式。這個問題與遍歷理論和馬爾可夫鏈有關。Matthews 獲得了以下對映表
|
(11)
|
其中 。
| 迴圈數 | 最大迴圈長度 | |
| 0 | 5 | 27 |
| 1 | 10 | 34 |
| 2 | 13 | 118 |
| 3 | 17 | 118 |
| 4 | 19 | 118 |
| 5 | 21 | 165 |
| 6 | 23 | 433 |
Matthews 和 Watts (1984) 提出了以下猜想。
1. 如果 ,則對於 Z 中的
,所有軌跡
最終都會迴圈。
2. 如果 ,則對於 Z 中的
,幾乎所有軌跡
都是發散的,但滿足以下條件的整數
的例外集合除外
|
(12)
|
3. 迴圈數是有限的。
4. 如果對於 Z 中的 ,軌跡
不是最終迴圈的,則迭代在 mod
下均勻分佈,對於每個
,有
|
(13)
|
對於 。
Matthews 認為對映
|
(14)
|
將達到 0 (mod 3) 或進入迴圈 或
之一,併為證明提供 100 美元(澳元?)的獎金。