考拉茲猜想（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₁<D₁，隨着迭代的繼續，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，因此考拉茲猜想對任何正整數都應該為真。

Base-X Conjecture and Collatz Conjecture Proof