續前文(三),雖然第三篇證明比前兩篇好,但總覺得說明還不夠好,所以希望以較簡潔明瞭的方式證明。
考拉茲函數為
任意正整數迭代運算後,目前已知結果會出現 fc = 1,今證明之。
證明
因為任一偶數 n 經過除二迭代運算後,最後皆會變成奇數,所以我們專注於奇數的處理。
令 x 為起始奇數,將 n = x 代入
Case 1: 3n+1 ≡ 0 (mod 4)
只要 3n+1 可被 4 整除,可推導出下一個迭代數不會大於起始奇數 x 。
1.a 如果 是奇數,當
若 ,那麼下一個迭代數值不會超過起始奇數 x 。
1.b 如果 是偶數,表示可以一直除二,直到成為奇數,
到此已證明,於 3n+1 ≡ 0 (mod 4) 情形下,下一個迭代數不會大於起始奇數 x,另外,
Case 2: 3n+1 ≡ 1 or 3 (mod 4)
如果想獲得餘數為 1 or 3,n 必為偶數,而 n 為偶數,就會被一直除二,直到成為奇數。
Case 3: 3n+1 ≡ 2 (mod 4)
因 為非整數,也表示 是奇數,那麼
將起始奇數 x 迭代入 fc(n) 應可得一漸增數列,
因為 p 是定值,沒有無窮大的 ,所以求解 數列過程中,一定會出現 偶數,
因而進入 Case 1 狀況。
以上分析完 所有狀況,欲證明重複迭代 fc(n) 會產生歸一的結果,如果直接證明 fc(n) 迭代歸一是困難的,那可以考慮兩種情形,一種是 fc(n) 迭代有漸增趨勢,另一種是 fc(n) 迭代有循環情形,只要證明這兩種狀況不存在,就可以說 fc(n) 迭代將會產生歸一狀況。
一、迭代循環
倘若有迭代循環,則必有某最小循環奇數 y,它必是 Case 3 型式,因為 Case 1 奇數的下一個迭代數不會比 y 大,除了 1 無法達成 y 是最小循環奇數條件。
而 Case 3 會產生漸增數值,經過迭代數次之後再除二回到原值 y。
奇數 n 經過 (3n+1)/2 計算
遇到偶數 /2 計算
從上面兩式計算過程可知,遇到奇數會一直累積 3 的倍數,這與回歸 y 循環 4, 8, 16, ... 除數完全沒有交集,因此 y 不會出現迭代循環情形。
二、迭代漸減
x 分別代入 1, 2, 3, ..., 皆為 3 的倍數
所以歸納出 為 3 的倍數
無論 Case 1 或 Case 3,當 出現 4 的倍數時
n 可以化約為 ,這將使 n 大幅變小,
又 Case 3 的 n 增幅有限,而它的 4p - 1 型式同 g(x),這將使 Case 3 多次迭代有機會變小。
2019年9月27日 星期五
完整非電腦證明考拉茲猜想 (四) (Collatz conjecture 4)
2019年9月23日 星期一
2019年9月19日 星期四
完整非電腦證明考拉茲猜想 (三) (Collatz conjecture 3)
https://4rdp.blogspot.com/2019/09/collatz-conjecture-3.html?m=0
續前文(二),由於 Case 1 證明還不夠嚴謹,並且 Case 3 證明也不夠清楚,所以再重新以另外形式證明。
考拉茲函數為
任意正整數迭代運算後,目前已知結果會出現 fc = 1,今證明之。
證明
因為任一偶數 n 經過除二迭代運算後,最後皆會變成奇數,所以我們專注於奇數的處理。
令 x 為起始奇數,將 n = x 代入
Case 1: 3n+1 ≡ 0 (mod 4)
只要 3n+1 可被 4 整除,可推導出下一個迭代數不會大於起始奇數 x 。
1.a 如果 是奇數,當
若 ,那麼下一個迭代數值不會超過起始奇數 x 。
1.b 如果 是偶數,表示可以一直除二,直到成為奇數,
到此已證明,於 3n+1 ≡ 0 (mod 4) 情形下,下一個迭代數不會大於起始奇數 x,另外,
Case 2: 3n+1 ≡ 1 or 3 (mod 4)
如果想獲得餘數為 1 or 3,n 必為偶數,而 n 為偶數,就會被一直除二,直到成為奇數。
Case 3: 3n+1 ≡ 2 (mod 4)
因 為非整數,也表示 是奇數,那麼
將起始奇數 x 迭代入 fc(n) 應可得一漸增數列,
因為 p 是定值,沒有無窮大的 ,所以求解 數列過程中,一定會出現 偶數,
因而進入 Case 1 狀況。
觀察下表,將得出下列結論:
藍字為 Case 3,紅字為 Case 1,只要兩個 Case 1 之間沒有 Case 3,就會發現最大的 Case 1 奇數,經過 fc(n) 迭代後,奇數 n 就會逐漸收斂到 1。
起始 n
|
起始奇數 n
|
(3n+1)/2
| ||||
1
2
4
8
|
1
4(1)-3
|
2
4(1)-2
|
1
4(1)-3
| |||
3
6
12
|
3
4(1)-1
|
5
4(2)-3
|
8
4(2)-0
|
1
4(1)-3
| ||
5
10
|
5
4(2)-3
|
8
4(2)-0
|
1
4(1)-3
| |||
7
14
|
7
4(2)-1
|
11
4(3)-1
|
17
4(5)-3
|
26
4(7)-2
|
13
4(4)-3
| |
9
|
9
4(3)-3
|
14
4(4)-2
|
7
4(2)-1
|
11
4(3)-1
|
17
4(5)-3
| |
11
|
11
4(3)-1
|
17
4(5)-3
|
26
4(7)-2
|
13
4(4)-3
| ||
13
|
13
4(4)-3
|
20
4(5)-0
|
5
4(2)-3
|
8
4(2)-0
|
1
4(1)-3
| |
15
|
15
4(4)-1
|
23
4(6)-1
|
35
4(9)-1
|
53
4(14)-3
|
80
4(20)-0
|
5
4(2)-3
|
接續證明 Case 1 的迭代收斂,若某數符合 4p-3 形式,
將 (4p-3) 和 (3p-2) 兩數相比較,,符合
因為起始奇數 x 為定值,所以 p 值也為常數,無論經過多少次 Case 3 將 增大,終將產生一個最大的 Case 1 數值 ,然後就會逐漸收斂到 1。
當 Case 1 迭代並且也無 Case 3 在其中時,p 值是會遞減,最後就歸一了。
故證明所有正整數經過 fc(n) 迭代計算都會歸一。
訂閱:
文章 (Atom)