3x+1 循环

我们仍没有关于除了简单的 4-2-1 循环外不存在其它正整数循环的证明. 然而我们知道不存在只含有 "很少" 元素的循环. 下面我们将给出更精确的结果.

现在关于 3x+1 循环的研究都是基于 Crandall 的一个定理. 在 1978 年他证明了如下定理:

Crandall 定理 (Crandall, 1978): 定义 3x+1 序列生成规则如下: 若 x 为奇数, 则下一项为 (3x+1)/2; 否则下一项为 x/2. 令 N₀ 为一个长度为 k 的正整数 3x+1 循环的最小数. 此外, 令 p_j / q_j 当 j > 4 时为 ln(3) / ln(2) 的最佳近似分数展开. 此时 k > (3/2) * min ( q_j , 2 * N₀ / (q_j + q_j+1)) 在参考资料这里可以找到详细证明.

想要利用这个定理来做精确有用的估计时, 首先我们要得到 ln(3) / ln(2) 的最佳近似分数展开. 显然我们没有什么简洁的方法来求出它们. 在硬算之后,我们可以得到关于分数展开的表格如下:

j	p_j	q_j
1	1	1
2	2	1
3	3	2
4	8	5
5	19	12
6	65	41
7	84	53
8	485	306
9	1,054	665
10	24,727	15,601
11	50,508	31,867
12	125,743	79,335
13	176,251	111,202
14	301,994	190,537
15	16,785,921	10,590,737
16	17,087,915	10,781,274
17	85,137,581	53,715,833
18	272,500,658	171,928,773
19	357,638,239	225,644,606
20	630,138,897	397,573,379
21	9,809,721,694	6,189,245,291
22	10,439,860,591	6,586,818,670
23	103,768,467,013	65,470,613,321

如果已知对于所有小于某个特定数 N 的数均收敛的话, 我们就能根据这个表格推断这时一个循环长度的下限.

例 :: 假设已知所有小于等于 1500 的数均收敛. 所以除了 4-2-1 以外, 没有别的循环拥有一个小于 1500 的元素. 暂时假定存在一个循环, 其中最小的元素为 1500. 现在从上表读出 j = 6 时候的数据. 我们看到 q₆ = 41. 2 * N₀ / (q_j + q_j+1) 的商, 也就是 2 * 1500 / (41+53) , 大约是 31. 由于 31 < 41 , 我们发现循环的长度不小于 3/2 * 31 = 47.

上面的例子说明了两件事情. 首先, 我们可以由最小的未检查收敛性的正整数 N 求得循环长度的下限. 其次, 循环长度下限不是随着 N 的增大而持续增大的, 而是依赖于 q_j 的值跳跃增大的.

对于所有 j 来说都有一个 N 的最大临界值 (记作 N_max). 当 N 大于这个值的时候, 它就不能继续提高循环长度的下限了. N_max 的值等于 q_j * (q_j + q_j+1) / 2 . 当 j = 6 时这个值为 N = 1927. 此时 q₆ = 2 * N₀ / (q₆ + q₇) , 定理的公式算出来的两个值是一样的. 一旦知道所有低于 1927 的数都是收敛的以后, 我们就可以得到此时循环长度的下限为 (3/2) * 41 , 也就是 62.

如果要继续提高循环长度的下限, 我们需要 j=7 的下一行. 尽管这样, 对于较小的 N 新的表达式的值比 41 要小, 所以暂时来说不能提升循环长度的下限. 只有当 N 达到关于 j 的最小临界值 (N_min) 的时候我们才能看到效果. 可以看到, N_min 的值为 q_j-1 * (q_j + q_j+1) / 2 . 当 j=7 时这个值为 N = 7360. 当取到这个值时, 2 * N₀ / (q₇ + q₈) 等于 41, 然后更大的 N 值就会使循环长度的下限提高.

当 j > 4 时这些临界值如下:
(注 : N_min 和 N_max 中较大的数已经被舍入)

j	q_j	N_min	N_max	k_min
1	1
2	1
3	2
4	5
5	12	132	318	18
6	41	564	1,927	62
7	53	7,360	9,513	80
8	306	25,732	148,563	459
9	665	2,488,698	5,408,445	998
10	15,601	15,783,110	370,274,134	23,402
11	31,867	867,431,201	1,771,837,067	47,801
12	79,335	3,035,921,290	7,558,126,447	119,003
13	111,202	11,969,231,783	16,776,990,139	166,803
14	190,537	599,449,615,674	1,027,115,802,069	285,806
15	10,590,737	2,036,079,429,954	113,172,673,831,054	15,886,106
16	10,781,274	341,535,948,748,930	347,680,491,387,159	16,171,911
17	53,715,833	1,216,368,161,954,000	6,060,343,986,623,000	80,573,750
18	171,928,773	10,677,992,615,805,000	34,177,151,614,467,000	257,893,160
19	225,644,606	53,574,551,736,291,000	70,312,888,338,719,500	338,466,909
20	397,573,379	743,140,051,792,797,000	1,309,718,777,460,900,000	596,360,069
21	6,189,245,291	2,539,711,459,647,450,000	39,537,096,854,067,000,000	9,283,867,937
22	6,586,818,670	222,990,560,815,925,000,000	237,314,619,175,287,000,000	9,880,228,005
23	65,470,613,321

结果表明当前知道循环长度的下限是很大的. 这是因为现在搜索的道德结果几乎断定了所有低于 500 . 10¹⁵ 的数都是收敛的. Tomás Oliveira e Silva 和作者 (参看当前状态) 分别使用不同的程序和硬件平台独立地对这些数进行了收敛性的检查. 尽管我们知道当我们在一台计算机上进行极长时间的计算时, 出错几乎是不可避免的, 但作者还是坚定地认为这些结果是正确的, 因为两个人单独的计算结果完全一致.

如果我们接受现今的计算结果, 认为所有小于等于 500 . 10¹⁵ 的数都是收敛的话, 由表格的第 19 行我们可以知道现在来说一个 3x+1 循环至少包含 338,466,909 (大约 3.3 亿) 个元素. 注意这个下限可能在一段时间内不能被提高, 因为这已经超出了第 19 行的最大临界值, 而要提高下限, 我们就需要证明直到 743 . 10¹⁵ 的数都是收敛的. 这需要大量的计算力.

最后, 我们考虑到在上面的定义中, 奇变换被定义为 (3x+1) / 2. 如果考虑原来的 3x+1 变换的话, 循环的长度就要再乘以一个因子 ln(6) / ln(3) ≈ 1.63, 这样的话现在知道的非平凡的循环长度至少是大约 5.53 亿.

参考资料 :: Crandall 的定理的证明可以在
R. E. Crandall, On the "3x+1" problem, Math Comp, 32 (1978) 1281-1292
找到.

鸣谢 :: 十分感谢 Vic Vyssotski 计算了第一个表格中的最佳近似分数展开, 他还对这些内容提供了他的意见.