科拉茨猜想

由 L. 科拉茨于 1937 年提出的问题，也称为映射、问题、哈塞算法、角谷猜想、锡拉丘兹算法、锡拉丘兹问题、Thwaites 猜想和乌拉姆问题 (Lagarias 1985)。Thwaites (1996) 为解决该猜想提供了 1000 英镑的奖励。设为一个整数。那么，科拉茨猜想的一种形式是询问迭代

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

(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) 修改，他询问迭代

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

(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) 还证明了整数集 $S_k={n:n has stopping time <=k}$ 具有极限渐近密度，这样，如果是满足且和的 n 的数量，则极限

(3)

存在。此外，当时，，因此几乎所有整数都具有有限的停止时间。最后，对于所有，

(4)

其中

			(5)
			(6)
			(7)

(Lagarias 1985)。

科拉茨猜想的推广让为正整数，, ..., 为非零整数。还让满足

(8)

然后

(9)

对于定义了一个广义科拉茨映射。一个等价的形式是

(10)

对于，其中 , ..., 是整数，是向下取整函数。这个问题与遍历理论和马尔可夫链有关。Matthews 获得了以下映射表

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

(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 中的，所有轨迹 ${T^K(n)}$ 最终都会循环。

2. 如果，则对于 Z 中的，几乎所有轨迹 ${T^K(n)}$ 都是发散的，但满足以下条件的整数的例外集合除外

(12)

3. 循环数是有限的。

4. 如果对于 Z 中的，轨迹 ${T^K(n)}$ 不是最终循环的，则迭代在 mod 下均匀分布，对于每个，有

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

(13)

对于。

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) 或进入循环或之一，并为证明提供 100 美元（澳元？）的奖金。

另请参阅

冰雹数, 杂耍者序列, Wolfram 序列

使用 Wolfram|Alpha 探索

更多尝试

参考文献

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

." 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

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. "科拉茨猜想。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CollatzProblem.html