考拉兹猜想(Collatz Conjecture)证明

考拉兹猜想（Collatz Conjecture）是数学中著名的未解难题之一。该猜想指出，
从任意正整数开始，反复应用两个小学生都懂的简单运算规则——“如果是偶数，
则除以2；如果是奇数，则乘以3并加1”，最终将得到1。尽管人们提出了各种各
样的方法和尝试，但考拉兹猜想仍然未被证明，因为还没有找到严格意义上的数
学证明。大多数研究都集中在将这两个简单的运算结合起来考虑，但如果将这两
个运算分开，并暂时保留除以2的运算结果，会发生什么呢？

若一个正整数D经过n次“乘以3加1（奇运算）”和m次“除以2（偶运算）”后变为1，
则可表示为：

D_n + Y_n = 2^m             [1]

其中Dn = 3n*D。对于任意正整数 D，如果基于考拉兹猜想迭代存在这样的 Yn，则考拉兹
猜想应该成立。现在需要做的是弄清楚Y是如何随着考拉兹猜想迭代而建立起来的，并且
这样的Yn存在。 对于任意正整数D，可以表示为2的k(0)次方（偶数部）与一个奇数（奇数部）
的乘积：
         D = 2k(0)(Q*2 + 1）                  [2] 
 现在，我们可以将考拉兹猜想迭代应用于奇数部，并收集除以2的次数并加入2k(0)部分。
 对于考拉兹猜想迭代，任何奇数到另一个奇数，都需要一次奇运算和一次或多次偶运算。
 例如： 

（1）数字 3:  3*3 + 1 = 10  → 5,

    一次奇运算和一次或多次偶运算, 收集1→ 2^k(0)+1

（2）数字 9:  3*9 + 1 = 28 →14 →7,

    一次奇运算和一次或多次偶运算, 收集2 → 2^k(0)+2

（3）数字 13:  3*13 + 1 = 40 →20 →10 → 5,

    一次奇运算和一次或多次偶运算, 收集3 → 2^k(0)+3

（4）数字 37:  3*37 + 1 = 112 → 56 → 28 → 14 → 7,

    一次奇运算和一次或多次偶运算, 收集4 → 2^k(0)+4

通常，对于公式 [2]，只需将考拉兹猜想迭代应用于奇数部（Q*2 + 1），然后收集除以 2的
次数，并将其加到偶数部，我们得到：

 2^k(0)[3(Q*2 + 1) + 1]

= 3*[2^k(0)(Q*2 + 1)] + 2^k(0)

= 3*D₁ + 2^k(0)

= D₁ + Y₁          D₁ = 3¹*D, Y₁ = 2^k(0), D₁ > Y₁    [3]

另一方面：

 2^k(0)[3(Q*2 + 1) + 1]

= 2^k(0)[3*Q*2 + 4]

= 2^k(0)+1[3*Q + 2]

= 2^k(0)+1*2^x*(Q₁*2 + 1)

= 2^k(0)+(1+x)*(Q₁*2 + 1)    收集1+x, x=0,1,2,...

= 2^k(1)*(Q₁*2 + 1)           k(1) = k(0)+(1+x)            [4]

经过一次奇运算和一次或多次偶运算之后，我们从公式 [2] 得到一个新的公式：

D₁ + Y₁ = 2^k(1)*(Q₁*2 + 1)     k(1) > k(0)      [5]

比较公式 [2]:

D→D1+Y1,2k(0)→2k(1)=2𝑘(0)+(1+𝑥),Q→ Q1

对公式 [5] 的奇数部分 (Q₁*2 + 1) 再进行 3n+1 并除以 2，可以得到：

 2^k(1)[3(Q₁*2 + 1) + 1]

= 3*[2^k(1)(Q₁*2 + 1)] + 2^k(1)

= 3*D₁ + 3* Y₁ + 2^k(1)

= D₂ + Y₂          D₂ = 3²*D, Y₂ = 3^* Y₁ + 2^k(1), D₂ >= Y₂

另一方面：

 2^k(1)[3(Q₁*2 + 1) + 1]

= 2^k(1)[3*Q₁*2 + 4]

= 2^k(1)+1[3* Q₁ + 2]

= 2^k(1)+(1+x)*(Q₂*2 + 1)      收集1+x, x=0,1,2,...

= 2^k(2)*(Q₂*2 + 1)         k(2) = k(1)+(1+x) , k(2)>k(1)

参照公式 [5]可以得到：

D₂ + Y₂ = 2^k(2)*(Q₂*2 + 1)

对奇数部分重复 3n+1 并除以 2 至步骤 n 我们可以得到：

D_n + Y_n = 2^k(n)*(Q_n*2 + 1) D_n = 3ⁿ*D, Y_n = 3^* Y_n-1 + 2^k(n-1)     [6]

上述过程可以理解为通过不断迭代趋近于2m，结合公式[1]和公式[6]可得到如下公式：
         2m-1 < Dn + Yn = 2k(n)(Qn*2 + 1) ≤ 2m                [7]

 设Y₀ = 0，则：

Y₁ = 2^k(0) = 3*Y₀ + 2^k(0)

可知 Y 的建立过程如下：

Y₀ = 0, Y₁ = 3*Y₀ + 2^k(0), Y₂ = 3^* Y₁ + 2^k(1),..., Y_n = 3^* Y_n-1 + 2^k(n-1)

k(0) < k(1) < k(2) < ... < k(n)

k的最小增量为1，对于任何奇数k(0)=0,k的最小序列为：

k = 0,1,2,3,..., n

Y的最小序列为：

Y = 0, 1, 5, 19, 65, 211, ..., 3ⁿ-2ⁿ.

综上所述，在考拉兹猜想迭过程中，D 和 Y 都乘以 3，D 保持不变，但 Y 每次增加 2^k，

且k也在增加，从而使得 Y 越来越大。一开始 Y₁1，随着迭代的继续，Y 会超过 D，

并在某一步从 Y ≤ D 变为 Y > D。

假设步骤n-1时 Y_n-1 ≤ D_n-1, 步骤n时 Y_n>D_n, 由公式 [7] 可得:

2^m-1 < D_n + Y_n = D_n + 3*Y_n-1 + 2^k(n-1) ≤ 2^m      [8]

2^m-1 < D_n + 3*Y_n-1 + Δ_n = 2^m                                                                     [9]

为确保从 Yn-1 ≤ Dn-1 到 Yn>Dn，2k(n-1)（Dn 与 3*Yn-1 之差）必须取可能的最大值。
根据公式 [8]，2k(n-1) 的最大值可能是 2m-1。但如果 2k(n-1) = 2m-1，则 Dn + 3*Yn-1 ≤ 2m-1，
从而导致 3*Yn-1 = 0 且 Dn = 2m-1。由于 Yn-1 不能为 0，因此 2k(n-1) 必定小于 2m-1，
最大可能值应为 2m-2。由此可知：

2^m-2 ≤ D_n < 2^m-1

2^m-2 ≤ 3* Y_n-1 < 2^m-1

2^m-1 < D_n + 3* Y_n-1 ≤ 2^m

从以上分析可得：

Δ_n = 2^k(n-1) = 2^m-2

由此可得：

3* Y_n-1 + Δ_n = 3* Y_n-1 + 2^k(n-1) = Y_n

由于对任何正整数都可找到满足方程 [1]的Yn，因此考拉兹猜想对任何正整数都应该为真。