2019年9月23日 星期一

訓練數學感 227 ─ 無限根號

http://4rdp.blogspot.com/2019/09/227.html



難度


2019年9月19日 星期四

完整非電腦證明考拉茲猜想 (三) (Collatz conjecture 3)

http://4rdp.blogspot.com/2019/09/collatz-conjecture-3.html

前文(二),由於 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) 迭代計算都會歸一。

2019年9月15日 星期日

完整非電腦證明考拉茲猜想 (二) (Collatz conjecture 2)

http://4rdp.blogspot.com/2019/09/collatz-conjecture-2.html

祝大家中秋愉快,前文已經部份證明出 考拉茲猜想 有正整數歸一的特性,今繼續完成補證。

考拉茲函數為  

任意正整數迭代運算後,目前已知結果會出現 fc = 1,今證明之。

證明

因為任一偶數經過除二迭代運算後,最後皆會變成奇數,所以我們專注於奇數的處理。







令 x 為最小不歸一奇數,將 n = x 代入

Case 1: 3n+1 ≡ 0 (mod 4)

只要 3n+1 對四整除,那就證明最小不歸一奇數 x 不存在,並且 fc(n) 會歸一(待補證明)

1.a 如果  是奇數,因為 x 是最小不歸一奇數,

而  ,就會不成立 x 是最小不歸一奇數,

因此 ,這表示最小不歸一奇數為 1,可是它仍然會 1,4,2,1,4,...歸一。

1.b 如果  是偶數,表示可以一直除二,直到成為奇數,



因為 ,所以不成立 x 是最小不歸一奇數。

Case 2: 3n+1 ≡ 1 or 3 (mod 4)

如果想獲得餘數為 1 or 3,n 必為偶數,而 n 為偶數,就會被一直除二,直到成為奇數,

所以此狀況不成立。

Case 3: 3n+1 ≡ 2 (mod 4)

只要迭代過程出現偶數,那就證明 fc(n) 會歸一。

 為非整數,則表示  是奇數,

當最小不歸一奇數 x 要符合 3x+1 ≡ 2 (mod 4) 特性,x ∈ {3, 7, 11, 15, 19, 23, ...},

也就是可轉化為   ,將它迭代入 fc(n) 應可得不歸一奇數數列,













若要  不歸一必須 p 有無窮大的 ,但是 p 為某定值,所以求解  數列過程中就會出現偶數,因而進入 Case 1 狀況,這在前面已證明不存在最小不歸一奇數,所以所有正整數都會歸一。

=======================================================================
觀察一
另外,任一奇數 n 可推算 fc(n) 下一個數為偶數 3n+1,再來是 





若 fc(n) 可接受非整除型態的  ,以有理數 r 代替 n,那麼 fc(n) 可改寫為 fq(r)





那麼經過多次迭代運算終將 fq(r) = 1,也就是有歸一特性。

=======================================================================
觀察二

這個問題也可以等效轉化為 n 為偶數時,令 f(n) = 0,去除後續不必要的計算,

還有當 n 為奇數時,3n+1 必為偶數,可縮減運算成 f(n) = (3n+1)/2,



簡單的說,任一奇數迭代過程不會出現偶數,就可以證明 f(n) 不是對所有正整數都會歸一,反之都會歸一。

從下圖可看出,迭代過程總會出現偶數,而且有規律可推算,也可以看出所有正整數經過 f(n) 迭代都會變成 0,所以沒有最小歸一奇數 x。