对于所有正整数 N 我们定义一个序列 Si, 其中
       S0 = N
     并且对于所有 i > 0 有: 
       Si = Si-1 / 2           如果 Si-1 是偶数
       Si = Si-1 * 3 + 1       如果 Si-1 是奇数

这个公式的特征给序列引出的一系列问题带来了一个名字, 就是 3x + 1 问题, 有时候又被称作角谷猜想(Collatz problem)或者其他别的什么名字.  对于 N = 13 我们有

   S0  = 13, S1  = 40, S2  = 20, S3  = 10, S4  =  5
   S5  = 16, S6  =  8, S7  =  4, S8  =  2, S9  =  1, S10 =  4 
从这里开始序列就进入了一个循环. 

注: 尽管这个序列的生成方法对于负整数也适合, 但本页面只讨论正整数(也被称作自然数).  所以在本页上的所有结果都应该被理解为只对正整数有效. 

我们现在定义

Mx(N)

Mx(N) = lim k → ∞ Max(S₀, S₁, ..., S_k)

Mn(N)

Mn(N) = lim k → ∞ Min(S₀, S₁, ..., S_k)

然后, 我们称一个正整数

收敛

当且仅当 Mn(N) = 1

发散

当且仅当 Mx(N) 不存在

循环

当且仅当上述两种情形均不成立

现今没有正整数 N 被发现可能是发散的, 所以我们广泛地相信以下的猜想, 尽管这个猜想并未被证明: 

猜想 1a: (弱 3x+1 猜想)

不存在发散的正整数 N . 

但现在有重要的迹象暗示可能除了简单的 4-2-1 循环以外, 再也没有其它的循环了. 事实上我们早已知道其它的循环必须有很长的周期.  对于现在循环问题的进展, 可以参见循环页面. 

所以, 现在有理由提出: 

猜想 1b: (强 3x+1 猜想)

所有的正整数 N 都收敛. 

现在这个猜想还未被证明. 

尽管很多研究这方面问题的研究者都把注意力集中到证明猜想 1b 上, 我们从这里开始假定猜想 1b 成立, 并在这个条件下探究 3x+1 序列的一些其它性质. 

滑翔步数(Glide)

对于所有正整数 N > 1 令 k 为满足 S_k < N 的最小下标. 
我们称 k 为 N 的滑翔步数(Glide)并记其为 G(N) . 

当所有比一个正整数小的所有正整数都收敛的时候, 计算这个正整数的滑翔步数跟验证它的收敛性是等价的. 
这样, 我们就可以重新叙述猜想 1b 如下: 

猜想 1b: (重新叙述的强 3x+1 猜想)

对于所有正整数 N > 1 , G(N) 均有限. 

显然, 这个猜想也未被证明.  然而 Terras 证明了一个较弱的重要定理: 

定理(Terras): 

对于几乎所有的正整数 N , G(N) 有限. 

如果你想看一个不太规范的证明, 请参阅 Terras 定理

任意高的滑翔步数都存在, 尽管这并非十分显然. 然而, 若观察任何形如 N = 2^p - 1 的数(此处 p > 1), 我们有 S₂ = 3 * 2^p-1 - 1 并且由于 S₂ 是奇数, S₄ = 3 * 3 * 2^p-2 - 1 并最终有 S_2p = 3^p - 1. 
因此 S_i 在 2p 步以内不会小于 N, 所以 G(N) > 2p. 

尽管滑翔步数无上界, 对于任意的 k 寻找较小的数字使 G(N) > k 仍然是困难的. 

滑翔步数记录(Glide Record)

一个正整数 N 被称为滑翔步数记录(Glide Record)
当且仅当对于所有正整数 M < N 均有 G(M) < G(N)

跳过平凡的数字 1 和 2 以后, 前几个滑翔步数记录是

   N =   3   G(N) =   6
   N =   7   G(N) =  11
   N =  27   G(N) =  96
   N = 703   G(N) = 132

等等.  作者在一个区间内计算了所有的滑翔步数, 现今发现的滑翔步数记录都被记录在滑翔步数记录表中. 

注: 关于滑翔步数记录的进展, 请参看当前状态 on Glide records.

归一步数(Delay)

对于所有的正整数 N 令 k 为满足 S_k = 1 的最小下标. 
我们称 k 为 N 的归一步数(Delay), 并记作 D(N). 

归一步数记录(Delay Record)

一个正整数 N 被称为归一步数记录(Delay Record)
当且仅当对于所有正整数 M < N 均有 D(M) < D(N). 

为了寻找归一步数记录, 人们已经进行了大量的计算. 
所有已知的归一步数记录都在归一步数记录表中给出了. 

注: 关于归一步数记录的进展, 请参看当前状态. 

剩余因子(Residue)

对于所有正整数 N , 令 E(N) 和 O(N) 分别表示从 S₀ 到 S_D(N)-1 中的偶数和奇数个数. 显然 O(N) + E(N) = D(N). 
参照 3x+1 序列的构造方法我们可以写出
2^E(N) = 3^O(N) * N * Res(N) 其中
(1 + 1 / ( 3 * S_i ) ) , 其中 S_i 为对于 0 ≤ i < D(N) 中所有的值为奇数的项. 
我们称 Res(N) 为 N 的剩余因子(Residue) of N.

计算结果表明, Res(N) 通常很小并处于 1.10 和 1.25 之间. 所以我们有理由猜测: 

猜想 2a: (弱剩余因子猜想)

存在一个实数 Res_max 使对所有正整数有
Res(N) < Res_max.

有重要迹象使我们有理由提出一个更精确的猜想: 

猜想 2b: (强剩余因子猜想)

对于所有正整数 N , Res(N) ≤ Res(993). 

关于支持这个猜想的证据可以参见“关于剩余因子”页面. 
无论猜想 2b 正确与否, 我们从这里以后假定至少有猜想 2a 成立, 并且 Res_max << 6. 

完整度(Completeness)

对于所有正整数 N > 1 , N 的完整度(Completeness), 记作 C(N), 被定义如下: C(N) = O(N) / E(N).

定理 1: 

对于所有正整数 N > 1: C(N) < ln(2)/ln(3) = 0.63092975...

证明: 

从上一节我们知道, 根据定义有
   2^E(N) = 3^O(N) * N * Res(N)
两边取对数并移项, 得到
   O(N) / E(N) = ln(2) / ln(3) - (ln(N) + ln(Res(N))) / (E(N).ln(3) )
最后一项通常很小, 但恒大于 0 . 

这就把我们引到了一个更复杂的问题, 那就是 C(N) 实际的值与它的理论极限有多接近. 如果上面的式子的最后一项无限趋近 0 的话, C(N) 也无限趋近它的理论极限. 对于足够大的 N , 最后一项与 ln(N) / E(N) 成正比. 这个量的倒数通常被定义为 Gamma. 

Gamma

对于所有正整数 N > 1 定义 Gamma(N) 为 E(N) / ln(N) . 

有许多证据表明, Gamma(N) 不会有任意大的值, 所以我们提出

猜想 3: 

存在一个实数 C_max 使对于所有正整数 N > 1 有 C(N) < C_max.
且 C_max < ln(2) / ln(3).

简单地说, 就是 C(N) 不会无限接近它的理论极限. 关于支持这个猜想的证据, 请参看“关于完整度”页面. 

完整度记录(Completeness Record)

正整数 N > 1 被称为完整度记录(Completeness Record)
当且仅当对所有正整数 M < N 均有 C(M) < C(N) . 

相似地, 我们有: 

Gamma 记录

正整数 N > 1 被称为 Gamma 记录
当且仅当对所有正整数 M < N 均有 Gamma(M) < Gamma(N) . 

从它们定义的相似性不难发现, 已知的完整度记录和 Gamma 记录其实是相同的. 

所有已知的完整度和 Gamma 记录可以参见完整度和 Gamma 记录表. 

注: 关于完整度和 Gamma 记录的进展, 请参看当前状态. 

假定猜想 1b 成立, 我们将所有正整数分成步数类(Delay class) DC_k (k=0,1,2,3...) 而正整数 N 被称为属于步数类 D(N).  我们注意到没有空的步数类, 这是由于当 N = 2^k 时, 我们有 D(N) = k . 

步数分类记录(Class Record)

步数类 DC_k 的最小元素 N 被称为这个步数类的步数分类记录(Class Record), 记作 R_k . 

连续的步数类的步数分类记录通常会“有联系(related)”.  'related', 步数较低的记录有时会在较高的记录的 3x+1 序列中出现. 假定猜想 2a 成立, 对于 Res_max < 6 我们有: 

定理 2: 

令 R_k 与 R_k+1 分别为步数类(Delay Classes) k 与 k + 1 的步数分类记录. 
那么 O(R_k) <= O(R_k+1) 并且 E(R_k) <= E(R_k+1) . 

证明: 

令 R_k 与 R_k+1 分别为步数类 k 和 k+1 的步数分类记录. 
假定 O(R_k) - O(R_k+1) = x, x > 0 .  那么 R_k+1 / R_k 等于 2^x+1 * 3^x * Res(R_k) / Res(R_k+1) , 这对于正实数 x 来说, 有 >> 2 . 
由于 N = 2 * R_k 的归一步数为 k + 1 而且比 R_k+1 要小,  这意味着 R_k+1 不会是步数分类记录. 
故 O(R_k) <= O(R_k+1) . 

假定 E(R_k) - E(R_k+1) = x, x > 0 .  这时有 R_k / R_k+1 等于 2^x * 3^x+1 * Res(R_k+1) / Res(R_k) , 这对于正实数 x 来说有 x >> 3 . 
由于 N = 3 * R_k+1 + 1 与 N = R_k+1 / 2 之中肯定有一个的归一步数为 k , 并且它们都小于 R_k . 这就表明了 R_k 不会是一个步数分类记录. 
故 E(R_k) <= E(R_k+1) . 

由上面的结果推广可得

定理 3: 

令 N 为一个完整度记录. 
那么 N 也是一个步数分类记录. 

证明: 

假定存在正整数 M < N 有 D(M) = D(N) . 

 •  如果 O(M) = O(N) , 那么我们有 E(M) = E(N) , 这时 C(M) = C(N) 所以 N 不符合完整度记录的定义, 不会是一个完整度记录. 
 •  如果 O(M) > O(N) 那么 C(M) > C(N) 这时 N 不符合完整度记录的定义, 也不会是一个完整度记录. 

 •  如果 O(M) < O(N) , 这时, 由于我们假定猜想 2a 成立, M 不会 < N . 故这样一个 M 不存在, 所以 N 是一个步数分类记录. 

理论上, 因为可能存在一些较小的数, 它们的归一步数很大但是完整度很低, 所以一个完整度记录不一定是一个归一步数记录. 尽管如此, 所有已知的完整度记录都是归一步数记录. 

2000 问题 对读者的一个智力挑战: 试找出 R2000的可能候选数字. 注意, 已知数字 N = 67457,283406,188652 的归一步数恰好是 2000 . 谁能改进这个结果？

所有已知的步数分类记录都被记录在步数分类记录表上. 

注: 关于步数分类记录的进展, 请参看当前状态. 

如果猜想 2a 成立, 并且 Rmax << 6 的话, 这就意味着一个步数类可以被分成离散的几个级别. 这些级别的数之间的大小基本上每一级相差六倍. 例如, 步数类 13 的元素为 34, 35, 192, 208, 212, 213, 226, 227, 1280, 1344, 1360, 1364, 1365 和 8192. 它们显然可以按照大小分成四个不同的“子类(subclasses)”. 
在探讨等级之前, 我们先定义一个更基本的概念: 强度(Strength). 

强度(Strength)

对于所有正整数 N , 当 D(N) = k 时, 我们将强度(Strength)记作 S(N), 并定义
S(N) = 5 * O(N) - 3 * E(N) . 

绝大多数正整数的强度都小于零, 强度为正的正整数很稀有. 尽管这样, 可以证明存在拥有任意大强度的数. 

强度记录(Strength Record)

正整数 N 被称为强度记录(Strength Record)
当且仅当对于所有 M < N 均有 S(M) < S(N).

强度记录极其稀少. 在 2⁵⁵ 以下, 只有 4 个非平凡的强度记录是已知的. 它们被记录在“关于强度” 页面上, 那上面还有几个已知最有可能为下一个强度记录的数. 
在强度的基础上, 我们可以容易地定义等级(Level). 注意到对于所有正整数 N,  若满足 D(N) = k 我们有 S(N) ≡ 5k (mod 8) . 这样我们就可以定义等级了. 

等级(Level)

对于所有满足 D(N) = k 的正整数 N , 它的等级(Level) 被记为 L(N), 并定义
L(N) = - [S(N) / 8 ]
(这里 [x] 表示小于等于 x 的最大整数)

由于 S(34) = 5 * 3 - 3 * 10 = -15 , 所以 L(34) = -[-15/8] = 2 . 相似地, L(192) = 3, L(1280) = 4 and L(8192) = 5 .  对于所有归一步数 k , 可能的最高等级在 N = 2^k 时取到, 因为这是归一步数为 k 的最大数字. 如果 C(N) >= 0.60 , 那么 N 的最高等级不超过 0 . 

对于较小的数, 由于样本不足, 统计得出的结果不甚可靠. 然而对于较大的数, 关于等级的统计给出了关于记录唯一性的一些信息. 从统计的观点上来看, 对于接近 0 的等级来说, 等级越低, 处于该等级的数字就越少. 尽管等级为负的正整数存在, 但它们却很稀有.  唯一一个低于 10,000,000,000 而且 L(N) < 0 的正整数为 N = 63,728,127 , 它的等级为 L(N) = -1 . 

紧接着的拥有负等级的正整数就是 L(12,235,060,455) = -1 (D(N) = 1184) 和 L(13,371,194,527) = -1 (D(N) = 1210) . 在 21,000,000,000 以下, 还有三个正整数的等级为 -1 , 但下一个等级为 -1 的数竟然直到 R₁₄₀₈ = 1,444,338,092,271 才出现. 这个数几乎是它的前一个等级为 -1 的数的 70 倍. 在九个等级为 -1 的数出现以后, 我们就碰到了等级为 -2 的一个数: R₁₅₄₉ = 3,743,559,068,799 .  这个数的归一步数大得令人惊异, 竟然超出了它之前的归一步数记录至少 100 . 

一直到 100,000,000,000,000 (10¹⁴) 我们才大约找到 100 个等级为 -1 的数和一个等级为 -2 的数. 这就显示了它们的稀有性. 尽管我们就在稍稍超出这个范围的地方令人吃惊地找到了第一个等级为 -3 的数. 这个数是 N = 100,759,293,214,567 .  这个数不仅以超出前一个归一步数记录 158 步的成绩成为又一个归一步数记录, 还是一个完整度记录. 下一个等级为 -3 的数引人注目地出现在 R₁₇₈₉ 这个归一步数记录处. 它是 N = 104,797,092,792,063 . 在 100 * 10¹² 与 531 * 10¹² 之间有 15 个等级为 -3 的数. 但是自此以后就很稀少了. 最近发现下一个等级为 -3 的数是 N = 12769,884180,266527 , 它的大小是之前一个等级为 -3 的数的 20 倍以上. 

拥有更低等级的数就更难以寻找了. 当数目增大时, 搜索变得更缓慢, 搜索的区间也会更大. 目前找到的等级为 -4 的一个候选数有 18 位, 等级为 -7 的有 22 位, 等级为 -10 的至少会有 38 位. 我们欢迎任何能给出更小的候选数的建议! 

所有正整数 N 都可以由它的归一步数、等级和剩余因子所决定并计算出来. 但是这些数字并没有给出关于 3x+1 序列 S_i 的路径的任何详细信息. 特别地, 我们没有任何关于 Mx(N) , 也就是路径中达到的最大的数字的信息. 但这个数字在实践中是很重要的, 因为它决定了一个计算 3x+1 序列的计算计算法需要使用多少个二进制位才能保证不溢出. 

最高点记录(Path Record)

正整数 N 被称为最高点记录(Path Record)
当且仅当对于所有正整数 M < N 均有 Mx(M) < Mx(N)

前几个最高点记录如下: 

   N =  2    Mx(N) =    2
   N =  3    Mx(N) =   16
   N =  7    Mx(N) =   52
   N = 15    Mx(N) =  160
   N = 27    Mx(N) = 9232

最高点记录可以简单地按照它们出现的次序编号. 因此 P₁ = 2, P₂ = 3 , 如此等等. 
关于 Mx(N) 的值, 我们有一个有趣的结果: 

定理 4: 

令 N > 2 为任意奇数. 如果 Mx(N) > 3N + 1 那么 Mx(N) ≡ 16 (mod 36).

证明: 

令 x 为 Mx(N) , 设 x ≡ a (mod 36) .  我们注意到因为 x 一定是一个偶数, 所以 a 不可能是奇数. 相似地, 我们注意到不可能有 a ≡ 2 (mod 4) , 否则 x/2 会是一个奇数, 那么按照 3x+1 序列的生成方法, 下一个数就会比 x 要大. 所以 a ≡ 0 (mod 4).
由于 x 一定是由一个 3x+1 迭代产生的, 所以我们有 a ≡ 1 (mod 3) . 所以 a 的可能值就只剩下 4, 16 和 28 了. 
假设 a = 4 , 那么令 x = 36n+4 . 这样,  x 的前驱就是 12n+1 . 所以 12n+1 的 前驱就是 24n+2 . 由于 24n+1 并非模 3 余 1, 所以它的前驱必定为 48n+4 . 然而这个数比 x 大, 这就引起了矛盾. 
相似地, 当 a = 28 时, 我们发现它的一系列前驱是 12n+9, 24n+18 与 48n+36, 也与 x 就是 Mx(N) 这个假定矛盾. 
所以 a 只能等于 16, 故有 Mx(N) ≡ 16 (mod 36)(这时它的前驱就是 12n+5, 24n+10 和 8n+3). 

对于所有最高点记录 P_i ≥ 3 我们显然有 Mx(P_i ) > 3.P_i + 1, 所以对于 i ≥ 2 , 我们有 Mx(P_i ) ≡ 16 (mod 36).

所有当前已知的最高点记录都被记录在最高点记录表中. 

注: 关于最高点记录的进展, 请参看当前状态. 

扩张度(Expansion)

对于特定的正实数 Q, 正整数 N 的扩张度 (Expansion) X_Q 的定义为
X_Q(N) = Mx(N) / N^Q

容易看出 X₁(N) 无上界, 因为当 N = 2^p - 1 时, 正如我们先前看到的,  S_2p = 3^p - 1 而且 Mx(N) / N 至少近似等于 3^p / 2^p . 

现在有一个更有趣的问题: 对于什么 p X_p 会有界. 我们熟知有下面的结果: 

定理 5: 

当 X_Q 时, Q < ln(3) / ln(2) 无界. 

证明: 

在前面我们看到, 对于 N = 2^p - 1 ,  Mx(N) 至少是 3^p - 1 . 
所以当 p 趋向于无穷时, 仍有 ln(X_Q( N )) = ln( Mx(N) ) - Q * ln( N ) >= p * ( ln(3) - Q * ln(2) )
所以对于 Q < ln(3) / ln(2) 上界不存在. 

如果以 ²log( Mx(P_i )) 为 x 轴,  ²log( P_i ) 为 y 轴作图像的话, 这条曲线有趋近于一条斜率为 2 的直线的趋势. 现在还不知道这种趋势会不会保持下去. 如果这种趋势保持下去的话, 那就意味着对于 X_Q(N) 时 Q > 2有界. 

未解问题 1: 

是否存在一个实数 C 使 X₂(N) < C 对于所有正整数 N 成立？
如果存在的话, C 的值是多少？

许多年来, 已知最大的 X₂(N) 在 P₆₂ (± 15.054)取到. 看起来在不远的将来发现拥有更大扩张度的数机会渺茫. 然而, 在2005年, Tomás Oliveira e Silva 发现 P₈₆ 的扩张度是更高的 ± 16.315 .  扩张度记录是很稀少的. 函数 X₂(N) 在 N = 27 取到极大值 12.66 , 并且保持这个记录直到 P₄₃ = 319,804,831 这一个比它大 10,000,000 倍的数. 再一次, P₄₃ 达到的函数极大值 13.83 直到 P₆₂ 才被超过, 这个数的函数值是 15.05 .  P₆₂ 比 P₄₃ 要大超过 10,000 倍. 最后, 当前已知的最大的扩张度在 P₈₆ 处取到. 这个数的扩张度达到了 16.32 . P₈₆ 比它的前一个记录要大上超过 500,000 倍. 

如果函数 X₂(N) 的记录值之间的间距情况还是这样的话, 我们可能只能得到几个扩张度记录. 

 •   在1999年8月 第一次关于 3x+1 问题的会议在 Eichstätt 举行. 
 •   这里有 Eichstätt 会议的一张很好的与会者的照片. 
 •   Lagarias 关于 3x+1 问题的概述. 
 •   关于 3x+1 问题及其推广的一个极其全面的索引. 
 •   Gary T. Leavens and Mike Vermeulen : 3x+1 search programs
     Computers Math. Applic. Vol. 24, No 11, pp. 79-99 (1992)
 •   Tomás Oliveira e Silva 是第一个寻找到直到 100 * 2⁵⁰ 的所有最高点记录和滑翔记录的人. 
     最近他把他的搜索扩展到大约 2⁶⁰.
 •   Colin Campbell 关于 3x+1 问题的页面, 里边也包含了几个有用的参考资料. 
 •   这个法文网页允许你自己来做计算. 
 •   Ken Conrow 的3n+1 问题的结构.
 •   这个由 Alfred Wassermann 编写的 3x+1 在线计算器可以处理一些颇大的数字. 
 •   Peter Schorer 对 3x+1 猜想有一个可能的证明. 在这里可以看到他的论文. 

只要还有计算力, 寻找新纪录的努力就会继续! 
但是当数字越来越大的时候, 取得进展所需要的 CPU 时间越来越长. 
现在我们有一个最新版本的软件, 运行时不需要任何的干预, 每个人只要他电脑的 CPU 有空闲时间, 都可以参加 3x+1 搜索! 参阅 3x+1 搜索这个页面来看看如何参与, 或者看看步数分类记录搜索的进展情况. 

特别鸣谢来自意大利的 Luigi Morelli , 他是第一个参加这个计划的人. 还有来自加拿大的 Kevin Hebb , 他花了大量的时间和精力在维持两个教室的电脑日夜不停地进行关于这个问题的搜索上面. 

如果有任何的建议或者请求, 请发邮件到