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。


這問題請教數學系的朋友,他說這是離散數學的領域,前人證明它採取最後變成  型態,而這個又與質數有關連,因為質數是毫無規則,使得這問題至今無人能證明它。

兩個新觀察是自己想的,最後 (3n+1) ≡ 2 (mod 4) 根據 Andy 的 4p + 3 想法修改後補證,因此這個證明算是父子我倆聯力合證,如果沒有 Andy 的突想,我應該不會去想證明這個問題。

有網友建議我們研讀前人的論文,這部份會再研究是否有人用過我們的方法,以及學習 coq 數學證明工具讓證明更嚴謹。

延伸閱讀

4 則留言:

  1. Case 3 一開始假設 x0 是最小的不歸一奇數, 接著證明迭代過程一定會出現 xk 是偶數, 因此套用 case 1 的結果推出 x0 不是最小的不歸一奇數, 是這樣子嗎?
    但是這樣的論證似乎是有問題的, 因為即使 xk 是偶數, 也無法斷定 xk/2 是比 x0 還小的奇數, 因為中間已經經過了 k 次會變大的迭代 (3n+1), 而非 case 1b 只有經過一次 3n+1

    回覆刪除
    回覆
    1. 從 case 1 所獲得的重要工具是在 3n+1 ≡ 0 (mod 4) 情況下,都會歸一,並不只有 x0 不是最小的不歸一奇數的結論。所以 xk 是偶數時,即符合 2xk = 3n+1 ≡ 0 (mod 4),也表示後面的迭代將出現歸一。

      刪除
    2. case 1 證明的結果是:若 x 是最小不歸一奇數,則 3x+1 != 0 (mod 4),反過來說就是:若 3x+1 == 0 (mod 4),則 x 不是最小不歸一奇數。所以頂多只能推論出 x 不是最小不歸一奇數,並沒有強到可以推出 x 一定會歸一。

      刪除
    3. mnnuahg 謝謝您的指正,Case 1的歸一特性,我再想想如何補證。

      刪除