【原】基于3x+1猜想的奇數(shù)體系構(gòu)建及分析20210819

基于3x+1猜想的奇數(shù)體系構(gòu)建及證明

張林峰²  呂智林¹

（1、廣西大學(xué)  電氣工程學(xué)院，廣西 南寧 530004）

（2、華藍設(shè)計（集團）公司，廣西 南寧530004）

摘要：通過分析奇數(shù)在3x+1猜想迭代過程中的特點，構(gòu)造了奇數(shù)的表達式，建立了相關(guān)的定理體系，在此基礎(chǔ)上構(gòu)建了相應(yīng)的奇數(shù)體系。假設(shè)存在不符合3x+1猜想的奇數(shù)，并構(gòu)建相應(yīng)的奇數(shù)體系。通過對比分析兩個不同的奇數(shù)系，可知任意大于1的奇數(shù)經(jīng)有限次迭代后不會等于其自身，也不會趨于無窮大，即3x+1猜想是正確的。

關(guān)鍵詞：3x+1猜想；數(shù)論函數(shù)；奇數(shù)系

中圖分類號：O156        文獻標識碼：A

Construction and Proof of Odd System Based on 3x +1 Conjecture

ZHANG Lin-feng²，LU Zhi-lin¹

(1.College of Electric Engineering, Guangxi University, Nanning, 530004, China)

(2.Guangxi Hualan Design & Consulting Group, Nanning, 530004, China)

Abstract: By analyzing the characteristics of odd numbers in the iterative process of 3x +1 conjecture, an odd number expression is constructed, and a related theorem system is established. Based on this, a corresponding odd number system is constructed. Assume that there are odd numbers that do not conform to the 3x +1 conjecture, and build the corresponding odd numbers system. By comparing and analyzing two different odd number systems, we can know that any odd number greater than 1 will not equal itself and will not tend to infinity after finite iterations, that is, 3x+1 conjecture is correct.

Key words: 3x+1 conjecture; Arithmetical function; odd system

3x+1猜想流行于二十世紀五十年代，也稱為科雷茲（Collatz）問題，其基本描述為：任給一自然數(shù)n，若n是偶數(shù)，則除以2，若n是奇數(shù)，則乘3加1。然后對得到的結(jié)果繼續(xù)進行上述操作，經(jīng)過有限次運算，最終的結(jié)果為1。

用數(shù)學(xué)語言描述就是：

任給n∈N，定義數(shù)論函數(shù)C(n)為：

                        （1）

3x+1猜想形式上非常簡單，因而引起了普遍的興趣，但實際上解決起來卻異常困難，迄今為止未被證明，成為一道著名的數(shù)學(xué)難題。針對這一問題的研究，主要從數(shù)論和數(shù)學(xué)分析兩個角度出發(fā)。

把3x+1猜想的表述改變一下，設(shè)初始正整數(shù)是n，上述操作得到的數(shù)列中一定有個最小值S(n)。那么3x+1猜想就是說。于是，很多數(shù)學(xué)家開始研究S(n)的性質(zhì)，比如去尋找S(n)可能的上界f(n)，即S(n)≤f(n)?；诟怕屎兔芏确植?，人們已經(jīng)取得了一些初步的成果：

1976和1977年，Terras、Everett相互獨立地證明了,幾乎對所有的正整數(shù)n(在自然密度意義下)，有S(n)≤n。1979年，Allouche證明了，對任意a>0.869，幾乎對所有的正整數(shù)n(在自然密度意義下)，有。1994年，Korec證明了，對任意a>ln3/ln4≈0.7924，幾乎對所有的正整數(shù)n(在自然密度意義下)，有。2019年，陶哲軒利用偏微分方程對上述一些成果進行了改進，證明了只要{f(n)}是一個趨于正無窮的實數(shù)列，那么幾乎對所有的正整數(shù)n(在對數(shù)密度意義下).有S(n)<f(n)。

本文在上述工作的基礎(chǔ)上，嘗試提出一種新的思路，通過構(gòu)建某種形式的奇數(shù)體系，試圖對這個問題進行探討。

1、三個定理的提出及證明

3x+1猜想所考慮的是全體自然數(shù)，顯然若所有的奇數(shù)（或偶數(shù)）都符合3x+1猜想，則全體自然數(shù)也符合3x+1猜想。下面，我們只考慮奇數(shù)。任取一個奇數(shù)n，作運算

，其中k是使偶數(shù)能被整除的最大自然數(shù)。則如（1）所示的Collatz函數(shù)可改寫為

                     （2）

   其中表示自然數(shù)中全體奇數(shù)的集合。根據(jù)上述公式，每一次迭代都會得到一個奇數(shù)。

如果一個奇數(shù)n符合3x+1猜想，即經(jīng)過有限次迭代運算后等于1，考慮把迭代過程用算式表達出來，則該奇數(shù)可以表達為：

        (3)

式中j,m,p_i為正整數(shù)，且，j為n迭代到1時乘3加1的次數(shù)，m為除以2的次數(shù)。比如7的迭代軌跡為：，則：

為便于敘述，定義函數(shù)S，若奇數(shù)n經(jīng)過有限次迭代得到1，即符合3x+1猜想，則，否則。提出定理如下：

定理1  對于奇數(shù)n,若，則；反之亦然，即若，則。

證  若，則奇數(shù)n可表示為

奇數(shù)4n+1可表示為：

從上式可以看出，，且4n+1與n 需要相同的運算次數(shù)到達1，只是第一步運算時，n要除以，而4n+1要除以。

若，則奇數(shù)4n+1可表示為

    在上式中，需要確保。由于，又因為n是奇數(shù)，所以在對4n+1進行第一步運算時，除數(shù)必然不小于，因此。所以若，則，且n與4n+1 需要相同的運算次數(shù)到達1，只是第一步運算時，n要除以，而4n+1要除以。

定理2  對于奇數(shù)n,且，若，則；反之亦然，即若，則。

證  若n為奇數(shù)，且，則n可表示為：，其中k為自然數(shù)。由于，則：

同時，

     由上式可知，的第一次迭代運算為乘3加1除以4，剩余的迭代過程與奇數(shù)n相同。

由于 乘3加1除以4后，其值為n，顯然如果，則

定理3  對于奇數(shù)n,且，若，則；反之亦然，即若，則。

證  若n為奇數(shù)，且，則n可表示為：，其中k為自然數(shù)。由于，則：

同時，

     由上式可知，的第一次迭代運算為乘3加1除以2，剩余的迭代過程與奇數(shù)n相同。

由于 乘3加1除以2后，其值為n，顯然如果，則

2、基于3x+1猜想的奇數(shù)體系的構(gòu)建

   依據(jù)上一節(jié)提出的三個定理，本節(jié)基于3x+1猜想構(gòu)建一個奇數(shù)體系。

先構(gòu)建一個基礎(chǔ)數(shù)列，令，，即1,5,21,85，…。不難證明，數(shù)列的通項公式為。根據(jù)定理1可知，數(shù)列中的每一項都滿足，且只需一步運算就等于1。

從數(shù)列的特點可知，其任意三個連續(xù)項除以3之后，余數(shù)必定是0、1、2，只是次序有所不同而已。若，則令，以為首項，根據(jù)基礎(chǔ)數(shù)列的構(gòu)建方式，構(gòu)建一個新的數(shù)列；同樣，若，則令，以為首項，根據(jù)基礎(chǔ)數(shù)列的構(gòu)建方式，構(gòu)建一個新的數(shù)列。根據(jù)定理2、3可知，數(shù)列中的每一項都滿足，且只需一步運算就等于。

對于新構(gòu)建的數(shù)列，重復(fù)上述步驟。

這樣，我們就構(gòu)建了一個奇數(shù)體系，體系中的每一個數(shù)n，都符合。模仿Collatz樹的形式，上述奇數(shù)體系可以表示為如圖1所示的形式。

圖1 基于3x+1猜想的奇數(shù)樹

Fig.1 The odd graph based of 3x+1 conjecture

對于上述奇數(shù)系或奇數(shù)樹，繼續(xù)證明兩個問題：1，若，則奇數(shù)n必包含于其中；2，按照上述法則構(gòu)建的奇數(shù)系中不存在任意兩個相等的元素，或者說，奇數(shù)樹中任意兩個不同位置的數(shù)不相等。

先證明第一個問題。

對于一個奇數(shù)n,若n經(jīng)過一步運算就等于1，則可得等式:

,即

當k為偶數(shù)時，n屬于基礎(chǔ)數(shù)列；當k為奇數(shù)時，容易證明n不是整數(shù)。由此可以進一步獲知，式（3）中m與p的差為偶數(shù)，若，則括號中的表達式含有因子3，可以約掉，所以為了保持表達式的唯一性，需要。由此可知，任何一個奇數(shù)n，如果只經(jīng)過一次迭代運算就得到，則n必屬于基礎(chǔ)數(shù)列。

基礎(chǔ)數(shù)列中的任一元素，若，則可表示為。若奇數(shù)n經(jīng)過一步運算就等于，則可得等式:

，即

根據(jù)上一步的分析可知，k必須為偶數(shù)，否則n不是整數(shù)，而最小的偶數(shù)為2。結(jié)合定理2可知，若奇數(shù)n經(jīng)過一步運算就等于，則n必屬于以為首項的數(shù)列，且。

同樣的道理，基礎(chǔ)數(shù)列中的任一元素，若，則可表示為。若奇數(shù)n經(jīng)過一步運算就等于，則可得等式:

，即

根據(jù)前述的分析可知，k必須為奇數(shù)，否則n不是整數(shù)，而最小的奇數(shù)為1。結(jié)合定理3可知，若奇數(shù)n經(jīng)過一步運算就等于，則n必屬于以為首項的數(shù)列，且。

基礎(chǔ)數(shù)列中的任一元素，若，則可表示為。若奇數(shù)n經(jīng)過一步運算就等于，則可得等式:

，即

顯然上式中的n不是整數(shù)，所以不存在這樣的奇數(shù)n。據(jù)此，我們可知：對任一奇數(shù)進行迭代的過程中出現(xiàn)的任一元素，滿足。

對于新得到的數(shù)列，可以采用同樣的分析方法。

綜上所述，可知對于任何一個奇數(shù)n，若，則n必屬于上述奇數(shù)系，即必然位于圖1 所示的奇數(shù)樹中。例如，經(jīng)過一次運算等于1的奇數(shù)必屬于數(shù)列：5，21，85，…；經(jīng)過一次運算等于5的奇數(shù)必屬于數(shù)列：3，13，53，…；經(jīng)過一次運算等于13的奇數(shù)必屬于數(shù)列：17，69，277，…；等等。

下面分析第二個問題，即同一個奇數(shù)不會出現(xiàn)在兩個不同的數(shù)列中，或者說，奇數(shù)樹中任意兩個不同位置的數(shù)不相等。

首先需要說明的是：圖1所示的奇數(shù)樹中，除起始位置的元素為1外，不存在其它值為1 的元素。由于整個奇數(shù)體系中的每一個數(shù)列都是從一個不等于1且模3不為0的數(shù)衍生出來的。由于1經(jīng)過一次迭代后其值仍為1，上述結(jié)論顯然成立。

假設(shè)存在兩個奇數(shù)a=b,位于奇數(shù)樹上不同的位置。當對a和b進行迭代運算時，如果經(jīng)過相同的迭代次數(shù)其值為1，由于運算規(guī)則相同，則每一次的迭代結(jié)果也相同，根據(jù)數(shù)列的生成和奇數(shù)樹的生成過程，顯然a、b不可能位于奇數(shù)樹上不同的位置。如果經(jīng)過不同的迭代次數(shù)其值為1，則迭代次數(shù)多的數(shù)會首先等于1，這與前述結(jié)論相矛盾。所以，上述奇數(shù)系中不會出現(xiàn)相同的元素，或者說，奇數(shù)樹中任意兩個不同位置的數(shù)不相等。

綜合上述的分析，可知我們基于3x+1猜想建立了一個完備的奇數(shù)系，即對于自然數(shù)中任意一個奇數(shù),若n經(jīng)過有限次迭代運算后等于1，即，則n必屬于該奇數(shù)系，位于圖1所示的奇數(shù)樹上。同時，該奇數(shù)系中的任一元素n，滿足。

根據(jù)上述論證，為便于后續(xù)分析，繼續(xù)引入兩個定理。

唯一性定理：對一個奇數(shù)進行迭代運算時，其每一步的結(jié)果都是唯一的。

根據(jù)算術(shù)基本定理，每個整數(shù)的素因子分解形式是唯一的，上述唯一性原理顯然成立。

緊湊性定理：在奇數(shù)n和4n+1之間，不存在任何整數(shù)，其經(jīng)過一次迭代后的值與n和4n+1經(jīng)過一次迭代后的值相等。

根據(jù)定理1可知，奇數(shù)n和4n+1經(jīng)過一次迭代運算后，其值相等，只是在迭代運算中若n除以，則4n+1需除以。

不妨令，則，

假設(shè)存在奇數(shù)m， ,經(jīng)過一次迭代運算后，其值也是g,則。對比n和4n+1的迭代值，h的取值應(yīng)滿足，由于h為正整數(shù)，則

所以 ，根據(jù)前述分析，由于，m不是整數(shù)，顯然緊湊性定理成立。

3、不存在其它的迭代循環(huán)或趨于無窮的情形

根據(jù)定理1、2、3，提出三個新的定理：

定理4  對于奇數(shù)n,若，則；反之亦然，即若，則。

定理5  對于奇數(shù)n,且，若，則；反之亦然，即若，則。

定理6  對于奇數(shù)n,且，若，則；反之亦然，即若，則。

由于定理4、5、6與定理1、2、3互為逆否命題，顯然成立。

假設(shè)在自然數(shù)中存在奇數(shù)n，滿足，z是其中的最小值。利用與上一節(jié)相類似的方法，構(gòu)建一個新的奇數(shù)系。

先構(gòu)建一個基礎(chǔ)數(shù)列，令，。根據(jù)定理4可知，數(shù)列中的每一項都滿足。

從數(shù)列的特點可知，其任意三個連續(xù)項除以3之后，余數(shù)必定是0、1、2，只是次序有所不同而已。若，則令，以為首項，根據(jù)基礎(chǔ)數(shù)列的構(gòu)建方式，構(gòu)建一個新的數(shù)列；同樣，若，則令，以為首項，根據(jù)基礎(chǔ)數(shù)列的構(gòu)建方式，構(gòu)建一個新的數(shù)列。根據(jù)定理5、6可知，數(shù)列中的每一項都滿足。

對于新構(gòu)建的數(shù)列，重復(fù)上述步驟。這樣就構(gòu)建了一個新的奇數(shù)系，如圖2所示。

圖2 基于最小值z的奇數(shù)樹

Fig.2 The odd graph based of z

一個大于1的奇數(shù)經(jīng)多次迭代后，如果不等于1，則存在兩種情況：等于其自身或趨于無窮大。

假設(shè)存在大于1的奇數(shù)z，經(jīng)過i次迭代后，等于其自身，則：

     （4）

由上式可得：

由于z 是大于1的奇數(shù)，顯然可得：

假設(shè)在圖1所示的奇數(shù)系中存在兩個數(shù) x和y，y經(jīng)過與式（4）相同的迭代過程后等于x，則：

        （5）

由式（4）、（5）可得：

                                             （6）

可得：

，即                   （7）

同時，由式（6）可得：

            （8）

由式（7）、（8）可得：

上式表明：如果存在大于1的奇數(shù)z，經(jīng)過i次迭代后，等于其自身，且在圖1所示的奇數(shù)系中存在兩個數(shù) x和y，y經(jīng)過相同的迭代過程后等于x，則。

下面討論如何在圖1所示的奇數(shù)系中求得 x和y。

式（5）經(jīng)k-1次迭代后可得：

不妨令x取圖1所示的奇數(shù)系中的基礎(chǔ)數(shù)列，則，只需一次迭代就等于1。根據(jù)前述分析可知，任意三個連續(xù)的，模3的值分別為0、1、2，只是順序有所不同。不妨令，的值為0、1或2。為保證方程的解為整數(shù)，根據(jù)定理1和定理3，式（5）中，若為奇數(shù)或偶數(shù)，則可選取不同的的值，使得的值模3的值為2或1(若為奇數(shù)，則選取，使的值模3的值為2；若為偶數(shù)，則選取，使的值模3的值為1)。

根據(jù)定理（2）、（3），可得為：

現(xiàn)證明上式中，任意三個連續(xù)的的值，其模3的值必為0、1、2。

不妨設(shè)，

根據(jù)上述兩個表達式可知，若為奇數(shù)，則：

若為偶數(shù)，則：

。

分析以上各式，可知結(jié)論成立。

式（5）經(jīng)k-2次迭代后可得：

因為是由經(jīng)一步迭代所得，，所以根據(jù)為奇數(shù)或偶數(shù)，則可選取不同的的值，使得的值模3的值為2或1。不妨令，的值為0、1或2。根據(jù)定理（2）、（3），可令為：。同樣可以證明，任意三個連續(xù)的的值，其模3的值必為0、1、2。

上述過程假設(shè)進行到第j 步時，依然成立，則：

對于上式，需要證明任意三個連續(xù)的的值，其模3的值必為0、1、2。

為證明上述結(jié)論，先證明如下引理：

引理1：對于任意正整數(shù)n, 為整數(shù)，且。

當n=1時，顯然成立。假設(shè)n=i時成立，討論n=i+1時的情況。

根據(jù)假設(shè)，可得，其中k為自然數(shù)。對上式只需討論即可。

綜上所述，可知引理1成立。

設(shè)，則。根據(jù)引理1，若為奇數(shù)，則；若為偶數(shù)，則。由此可知，任意三個連續(xù)的的值，其模3的值必為0、1、2。因此，可以繼續(xù)構(gòu)造

最終，可得：

   （9）

經(jīng)過與式（5）相同的迭代步驟，可得

為說明上述過程，不妨設(shè)，以此為例構(gòu)造相應(yīng)的y和x。

上式經(jīng)一次迭代后，可得：。根據(jù)前述分析可知，若，則也為正整數(shù)，根據(jù)基礎(chǔ)數(shù)列的性質(zhì)，可令，即，相應(yīng)的可得：

上式中若i=0,。由于4為偶數(shù)，根據(jù)相應(yīng)數(shù)列的性質(zhì)，可得。根據(jù)上述公式，可得不定方程中的x若屬于圖1所示奇數(shù)系中的基礎(chǔ)數(shù)列，則其解的序列為：

根據(jù)上述分析和式（9）可知，對于任意一個式（4）所示的形式，都可以求得數(shù)列，使得經(jīng)過相同的迭代過程后等于，且屬于圖1所示的奇數(shù)系。根據(jù)式（9）可知，隨著i的增大，將逐步增大，i趨于無窮大時，也將趨于無窮大。但是根據(jù)式（8）可知，若式（4）成立，則。所以滿足式（4）的最小正奇數(shù)z不存在。因此可得結(jié)論：任意大于1的奇數(shù)經(jīng)有限次迭代后不會等于其自身。

根據(jù)上述結(jié)論可知，圖2所示的奇數(shù)系中，不存在任意兩個相等的元素。假設(shè)存在兩個相等的元素p、q，二者分別是由、衍生而得，其中。則p、q經(jīng)有限次迭代后都等于，根據(jù)唯一性原理，如果二者的迭代次數(shù)不相等，則迭代次數(shù)多的元素的迭代過程中會出現(xiàn)與相等的值，與上述結(jié)論相悖，如果迭代次數(shù)相等，則二者應(yīng)該出現(xiàn)在相同的位置。

下面討論是否存在大于1的奇數(shù)，經(jīng)過多次迭代后趨于無窮大。假設(shè)存在這樣的最小的奇數(shù)z，經(jīng)過i次迭代后等于。每一次迭代后未必大于，但是隨著i的逐漸增大，將趨向無窮大。則：

           （10）

對上式中m和i的大小，有如下結(jié)論：對于任意有限大的正奇數(shù)迭代到一定的次數(shù)時，必存在。

由于對一個奇數(shù)乘3加1后，必為偶數(shù)，因此迭代一次至少要除以2，即。

任意一個正奇數(shù)n都可表示為二進制形式：，。由于n為奇數(shù)，顯然。下面證明：若為上述表達式中自右起第一個為0的數(shù)，則對n迭代到第w次除以時，其中的。

若，則，結(jié)論顯然成立。

若，則可令，，可見經(jīng)過一次乘3加1除以2的迭代運算后，迭代結(jié)果的二進制形式中成為了表達式中自右起第一個為0的數(shù)。以此類推，可知每經(jīng)過一次同樣的迭代運算，第一個為0的數(shù)就向右移動一位，迭代到第w次時，，結(jié)論成立。

若的所有位數(shù)都為1，則，，顯然經(jīng)一次迭代后，迭代結(jié)果的二進制式中。

綜上所述，結(jié)論成立。

式（10）可改寫為：

令，則。

顯然，、為不定方程的一個解。由于，可知該方程有無窮多整數(shù)解。其解可表示為：

，其中t為整數(shù)。

由于x,y為正奇數(shù)，上式可改寫為：

，其中 k為整數(shù)。

不妨假設(shè)為不定方程的最小正奇數(shù)解,則：

，其中 k為非負整數(shù)。

根據(jù)上述分析可知，隨著迭代次數(shù)i的增加，m也不斷增大。當i足夠大時，，，上式中k只能為0。由此可知，式（10）所示的迭代過程中，當i足夠大時，、為不定方程的最小正奇數(shù)解。

另外，對于不定方程，若為方程的一組特解解，則其通解為：

，其中 k為整數(shù)。

由上式可知不定方程必存在正整數(shù)解，不妨設(shè)為其一組正整數(shù)解，則為不定方程的一組正整數(shù)解。由此可得：

由式（12）可得：。由于z是一個固定的數(shù)，，則。

把k的值帶入式（11），可得：，即。

由上述結(jié)論可得：，即。

但是根據(jù)、為不定方程的一個解，可得，由于z是一個固定的正奇數(shù)，顯然。上述結(jié)論相互矛盾的，由此可知：不存在大于1的奇數(shù)，經(jīng)過多次迭代后趨于無窮大。

根據(jù)上述分析可知，任意大于1的奇數(shù)經(jīng)有限次迭代后不會等于其自身，也不會趨于無窮大，即圖2所示的奇數(shù)系是不存在的。進而可知3x+1猜想是正確的。

5、進一步的討論

根據(jù)上述的討論可知，我們建立了一個完備的奇數(shù)體系，且對于任一奇數(shù)，，滿足。數(shù)的體系有不同的表達方式，諸如二進制、十進制、六十進制、羅馬數(shù)系等等，每種數(shù)系展現(xiàn)不同的特點。用本文的方法建立的數(shù)系能夠順利地解釋3x+1猜想。

在對3x+1猜想進行討論時，人們往往會考慮是否存在迭代的最小停止次數(shù)K和最小上界M，即對任意自然數(shù)進行迭代運算時，最多K次就等于1，迭代過程中出現(xiàn)的值都不大于M。這樣的K和M是不存在的。

假設(shè)存在這樣的K和M，令，其迭代過程為：

從上式可以看出，只要令，則n的停止次數(shù)大于K、迭代過程中出現(xiàn)的值大于M。

基于3x+1猜想，人們進而會考慮nx+1問題，比如5x+1或7x+1問題。對于這樣的問題可以采用同樣的方法進行分析。以5x+1或7x+1問題為例，可以用以下形式表示奇數(shù)：

對于前者可以用的模式產(chǎn)生數(shù)列，后者可以用的模式產(chǎn)生數(shù)列，具體細節(jié)有待進一步的分析。

本文中曾假設(shè)存在不符合3x+1猜想的最小的正奇數(shù)z，然后根據(jù)相應(yīng)的規(guī)則構(gòu)建了圖2所示的奇數(shù)系。比較圖1、圖2兩個不同的奇數(shù)系，如果采用解析數(shù)論等方法，在自然密度意義上進行分析，可能會得出更有意義的結(jié)論。

參 考 文 獻 ：

[1] Lagarias J C. The 3x+1Problem and Its Generalizations. Amer. Math. Monthly,1985,(92):3~23．

[2] Terrs R. A Stopping Time Problem on the Positive Integers．Acta Arith. 1976，(30)：241~252．

[3] Everett C J. Iteration of the Number-Theoretic Function f(2n)=n,f(2n+1)=3n+2. Advances in Math.,1977,(25):42~45．

[4] Lagarias J C. The Ultimate Challenge: the 3x+1 problem[M]. American Mathematical Society,2010．

[5] Collatz L. 關(guān)于（3n+1）問題的起因[J]，任志平，譯。曲阜師范大學(xué)學(xué)報（自然科學(xué)版），1986（3）：9~11.

[6] CHEN Tieling．Discoveries on Collatz Conjecture．Journal of Qufu Normal University, Jan.2020, Vol. 46 No.1:11~18.