主題
Search

科拉茨猜想


由 L. 科拉茨於 1937 年提出的問題,也稱為 3x+1 對映、 3n+1 問題、哈塞演算法、角谷猜想、錫拉丘茲演算法、錫拉丘茲問題、Thwaites 猜想和烏拉姆問題 (Lagarias 1985)。Thwaites (1996) 為解決該猜想提供了 1000 英鎊的獎勵。設 a_0 為一個整數。那麼,科拉茨猜想的一種形式是詢問迭代

 a_n={1/2a_(n-1)   for a_(n-1) even; 3a_(n-1)+1   for a_(n-1) odd
(1)

對於正數 a_0 是否總是返回到 1。(如果包括負數,則有四個已知的迴圈(不包括平凡的 0 迴圈):(4, 2, 1)、(-2, -1)、(-5, -14, -7, -20, -10) 和 (-17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34)。)

序列產生的科拉茨猜想的成員有時被稱為冰雹數。Conway 證明了原始的科拉茨猜想沒有長度小於 <400 的非平凡迴圈。Lagarias (1985) 表明,沒有長度小於 <275000 的非平凡迴圈。Conway (1972) 還證明了科拉茨型別的猜想在形式上可能是不可判定的。Kurtz 和 Simon (2007) 證明了科拉茨猜想的自然推廣是不可判定的;不幸的是,這個證明不能應用於原始的科拉茨猜想。

科拉茨演算法已經過測試,發現對於所有小於等於 <=19·2^(58) approx 5.48×10^(18) (約 5.48×10^(18))的數字,總是能達到 1 (Oliveira e Silva 2008),改進了早期的 10^(15) (Vardi 1991, p. 129) 和 5.6×10^(13) (Leavens and Vermeulen 1992) 的結果。由於解決這個問題非常困難,Erdős 評論說“數學尚未為解決此類問題做好準備” (Lagarias 1985)。

下表給出了前幾個起始值獲得的序列 (OEIS A070165)。

a_0a_0, a_1, a_2, ...
11
22, 1
33, 10, 5, 16, 8, 4, 2, 1
44, 2, 1
55, 16, 8, 4, 2, 1
66, 3, 10, 5, 16, 8, 4, 2, 1
CollatzSteps

演算法達到 1 所需的步數,對於 a_0=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)。產生包含 n=1, 2, ... 的科拉茨序列的最小起始值 a_0 分別是 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 時需要進位操作,在最壞的情況下,進位操作可能會擴充套件到基數-b 位表示的整個長度(因此需要以快於 CA 光速的速度傳播資訊)。

科拉茨猜想被 Terras (1976, 1979) 修改,他詢問迭代

 t_n={1/2t_(n-1)   for t_(n-1) even; 1/2(3t_(n-1)+1)   for t_(n-1) odd
(2)

對於初始整數值 t_0 是否總是返回到 1(例如,Lagarias 1985, Cloney et al. 1987)。這只是上面的原始陳述,但如果 t_(n-1) 是奇數,則將除以 2 的步驟合併到加法步驟中,從而壓縮了步數。下表給出了前幾個起始值 t_0=1, 2, ... 的序列 (OEIS A070168)。

t_0t_1, t_2, ...
11
22, 1
33, 5, 8, 4, 2, 1
44, 2, 1
55, 8, 4, 2, 1
66, 3, 5, 8, 4, 2, 1
77, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1

如果包括負數,則有 4 個已知的迴圈:(1, 2)、(-1)、(-5, -7, -10) 和 (-17, -25, -37, -55, -82, -41, -61, -91, -136, -68, -34)。它是“廣義科拉茨猜想”的一個特例,其中 d=2, m_0=1, m_1=3, r_0=0r_1=-1。Terras (1976, 1979) 還證明了整數集 S_k={n:n has stopping time <=k} 具有極限漸近密度 F(k),這樣,如果 N_x(k) 是滿足 nn<=xsigma(n)<=k 的 n 的數量,則極限

 F(k)=lim_(x->infty)(N_x(k))/x,
(3)

存在。此外,當 k->infty 時,F(k)->1,因此幾乎所有整數都具有有限的停止時間。最後,對於所有 k>=1

 1-F(k)=lim_(x->infty)(N_x(k))/x<=2^(-etak),
(4)

其中

H(x)=-xlgx-(1-x)lg(1-x)
(5)
theta=1/(lg3)
(6)
eta=1-H(theta)=0.05004...
(7)

(Lagarias 1985)。

科拉茨猜想的推廣讓 d>=2正整數m_0, ..., m_(d-1)非零整數。還讓 r_i in Z 滿足

 r_i=im_i (mod d).
(8)

然後

 T(x)=(m_ix-r_i)/d
(9)

對於 x=i (mod d) 定義了一個廣義科拉茨對映。一個等價的形式是

 T(x)=|_(m_ix)/d_|+X_i
(10)

對於 x=i (mod d),其中 X_0, ..., X_(d-1)整數|_r_|向下取整函式。這個問題與遍歷理論馬爾可夫鏈有關。Matthews 獲得了以下對映表

 T_k(x)={1/2x   for x=0 (mod 2); 1/2(3x+k)   for x=1 (mod 2),
(11)

其中 k=T_(5^k)

k迴圈數最大迴圈長度
0527
11034
213118
317118
419118
521165
623433

Matthews 和 Watts (1984) 提出了以下猜想。

1. 如果 |m_0...m_(d-1)|<d^d,則對於 Z 中的 n in Z,所有軌跡 {T^K(n)} 最終都會迴圈。

2. 如果 |m_0...m_(d-1)|>d^d,則對於 Z 中的 n in Z,幾乎所有軌跡 {T^K(n)} 都是發散的,但滿足以下條件的整數 n 的例外集合除外

 #{n in S|-X<=n<X}=o(X).
(12)

3. 迴圈數是有限的。

4. 如果對於 Z 中的 n in Z,軌跡 {T^K(n)} 不是最終迴圈的,則迭代在 mod d^alpha 下均勻分佈,對於每個 alpha>=1,有

 lim_(N->infty)1/(N+1)card{K<=N|T^K(n)=j (mod d^alpha)} 
 =d^(-alpha)
(13)

對於 0<=j<=d^alpha-1

Matthews 認為對映

 T(x)={7x+3   for x=0 (mod 3); 1/3(7x+2)   for x=1 (mod 3); 1/3(x-2)   for x=2 (mod 3)
(14)

將達到 0 (mod 3) 或進入迴圈 (-1)(-2,-4) 之一,併為證明提供 100 美元(澳元?)的獎金。


另請參閱

冰雹數, 雜耍者序列, Wolfram 序列

使用 探索

參考文獻

Applegate, D. and Lagarias, J. C. "3x+1 問題的密度界限 1. 樹搜尋方法。" Math. Comput. 64, 411-426, 1995.Applegate, D. and Lagarias, J. C. "3x+1 問題的密度界限 2. Krasikov 不等式。" Math. Comput. 64, 427-438, 1995.Bruschi, M. "用於 3x+1 對映的兩個細胞自動機。" http://arxiv.org/abs/nlin/0502061/. 26 Feb, 2005.Burckel, S. "Functional Equations Associated with Congruential Functions." Theor. Comp. Sci. 123, 397-406, 1994.Cloney, T.; Goles, E.; and Vichniac, G. Y. "3x+1 問題:準細胞自動機。" Complex Sys. 1, 349-360, 1987.Conway, J. H. "不可預測的迭代。" Proc. 1972 Number Th. Conf., University of Colorado, Boulder, Colorado, pp. 49-52, 1972.Crandall, R. "關於 '3x+1' 問題。" Math. Comput. 32, 1281-1292, 1978.De Mol, L. "標籤系統和類科拉茨函式。" Theor. Comput. Sci. 390, 92-101, 2008.Everett, C. "Iteration of the Number Theoretic Function f(2n)=n, f(2n+1)=f(3n+2)." Adv. Math. 25, 42-45, 1977.Guy, R. K. "科拉茨序列。" §E16 in 數論中未解決的問題,第二版。 New York: Springer-Verlag, pp. 215-218, 1994.Kurtz, S. A. and Simon, J. "廣義科拉茨猜想的不可判定性。" In 計算模型理論與應用:2007 年 5 月 22-25 日在上海舉行的第四屆國際會議 (TAMC 2007) 論文集 (Ed. J.-Y. Cai, S. B. Cooper, and H. Zhu). Berlin: Springer, pp. 542-553, 2007.Lagarias, J. C. "3x+1 問題及其推廣。" Amer. Math. Monthly 92, 3-23, 1985.Leavens, G. T. and Vermeulen, M. "3x+1 搜尋程式。" Comput. Math. Appl. 24, 79-99, 1992.Margenstern, M. and Matiyasevich, Y. "3x+1 問題的二項式表示。" Acta Arith. 91, 367-378, 1999.Matthews, K. R. "廣義 3x+1 對映。" http://www.numbertheory.org/pdfs/survey.pdf.Matthews, K. R. "廣義 3x+1 猜想。" [$100 美元證明獎金。] http://www.numbertheory.org/gnubc/challenge.Matthews, K. R. and Watts, A. M. "哈塞的錫拉丘茲演算法推廣的推廣。" Acta Arith. 43, 167-175, 1984.Oliveira e Silva, T. "3x+1 問題的最大偏移和停止時間記錄保持者:計算結果。" Math. Comput. 68, 371-384, 1999.Oliveira e Silva, T. "3x+1 猜想的計算驗證。" Sep. 19, 2008. http://www.ieeta.pt/~tos/3x+1.html.Schroeppel, R.; Gosper, R. W.; Henneman, W.; and Banks, R. Item 133 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 64, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/flows.html#item133.Sloane, N. J. A. Sequences A006577/M4323, A006666/M3733, A006667/M0019, A070165, A070166, A070167, A070168, in "The On-Line Encyclopedia of Integer Sequences."Terras, R. "正整數上的停止時間問題。" Acta Arith. 30, 241-252, 1976.Terras, R. "關於密度的存在性。" Acta Arith. 35, 101-102, 1979.Thwaites, B. "兩個猜想,或如何贏得 1100 英鎊。" Math. Gaz. 80, 35-36, 1996.Vardi, I. "3x+1 問題。" Ch. 7 in Mathematica 中的計算娛樂。 Redwood City, CA: Addison-Wesley, pp. 129-137, 1991.Wirsching, G. J. "Über das 3n+1 Problem." Elem. Math. 55, 142-155, 2000.Wolfram, S. 一種新科學。 Champaign, IL: Wolfram Media, pp. 100, 122, and 904, 2002.Zeleny, E. "作為細胞自動機的科拉茨猜想。" http://demonstrations.wolfram.com/CollatzProblemAsACellularAutomaton/.

請引用為

韋斯坦, 埃裡克·W. "科拉茨猜想。" 來自 Web 資源。 https://mathworld.tw/CollatzProblem.html

主題分類