基于3x+1猜想的奇数体系构建及分析20210819
基于3x+1猜想的奇数体系构建及证明
张林峰2 吕智林1
（1、广西大学 电气工程学院，广西 南宁 530004）
（2、华蓝设计（集团）公司，广西 南宁530004）
摘要：通过分析奇数在3x+1猜想迭代过程中的特点，构造了奇数的表达式，建立了相关的定理体系，在此基础上构建了相应的奇数体系。假设存在不符合3x+1猜想的奇数，并构建相应的奇数体系。通过对比分析两个不同的奇数系，可知任意大于1的奇数经有限次迭代后不会等于其自身，也不会趋于无穷大，即3x+1猜想是正确的。
关键词：3x+1猜想；数论函数；奇数系
中图分类号：O156 文献标识码：A
Construction and Proof of Odd System Based on 3x +1 Conjecture
ZHANG Lin-feng2，LU Zhi-lin1
(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）问题，其基本描述为：任给一自然数n，若n是偶数，则除以2，若n是奇数，则乘3加1。然后对得到的结果继续进行上述操作，经过有限次运算，最终的结果为1。
用数学语言描述就是：
任给n∈N，定义数论函数C(n)为：
（1）
3x+1猜想形式上非常简单，因而引起了普遍的兴趣，但实际上解决起来却异常困难，迄今为止未被证明，成为一道著名的数学难题。针对这一问题的研究，主要从数论和数学分析两个角度出发。
把3x+1猜想的表述改变一下，设初始正整数是n，上述操作得到的数列中一定有个最小值S(n)。那么3x+1猜想就是说
。于是，很多数学家开始研究S(n)的性质，比如去寻找S(n)可能的上界f(n)，即S(n)≤f(n)。基于概率和密度分布，人们已经取得了一些初步的成果：
1976和1977年，Terras、Everett相互独立地证明了,几乎对所有的正整数n(在自然密度意义下)，有S(n)≤n。1979年，Allouche证明了，对任意a>0.869，几乎对所有的正整数n(在自然密度意义下)，有
。1994年，Korec证明了，对任意a>ln3/ln4≈0.7924，几乎对所有的正整数n(在自然密度意义下)，有
。2019年，陶哲轩利用偏微分方程对上述一些成果进行了改进，证明了只要{f(n)}是一个趋于正无穷的实数列，那么几乎对所有的正整数n(在对数密度意义下).有S(n)<f(n)。
本文在上述工作的基础上，尝试提出一种新的思路，通过构建某种形式的奇数体系，试图对这个问题进行探讨。
1、三个定理的提出及证明
3x+1猜想所考虑的是全体自然数，显然若所有的奇数（或偶数）都符合3x+1猜想，则全体自然数也符合3x+1猜想。下面，我们只考虑奇数。任取一个奇数n，作运算
，其中k是使偶数
能被
整除的最大自然数。则如（1）所示的Collatz函数可改写为
（2）
其中
表示自然数中全体奇数的集合。根据上述公式，每一次迭代都会得到一个奇数。
如果一个奇数n符合3x+1猜想，即经过有限次迭代运算后等于1，考虑把迭代过程用算式表达出来，则该奇数可以表达为：
(3)
式中j,m,pi为正整数，且
，j为n迭代到1时乘3加1的次数，m为除以2的次数。比如7的迭代轨迹为：
，则：
为便于叙述，定义函数S，若奇数n经过有限次迭代得到1，即符合3x+1猜想，则
，否则
。提出定理如下：
定理1 对于奇数n,若
，则
；反之亦然，即若
，则
。
证 若
，则奇数n可表示为
奇数4n+1可表示为：
从上式可以看出，
，且4n+1与n 需要相同的运算次数到达1，只是第一步运算时，n要除以
，而4n+1要除以
。
若
，则奇数4n+1可表示为
在上式中，需要确保
。由于
，又因为n是奇数，所以在对4n+1进行第一步运算时，除数必然不小于
，因此
。所以若
，则
，且n与4n+1 需要相同的运算次数到达1，只是第一步运算时，n要除以
，而4n+1要除以
。
定理2 对于奇数n,且
，若
，则
；反之亦然，即若
，则
。
证 若n为奇数，且
，则n可表示为：
，其中k为自然数。由于
，则：
同时，
由上式可知
，
的第一次迭代运算为乘3加1除以4，剩余的迭代过程与奇数n相同。
由于
乘3加1除以4后，其值为n，显然如果
，则
定理3 对于奇数n,且
，若
，则
；反之亦然，即若
，则
。
证 若n为奇数，且
，则n可表示为：
，其中k为自然数。由于
，则：
同时，
由上式可知
，
的第一次迭代运算为乘3加1除以2，剩余的迭代过程与奇数n相同。
由于
乘3加1除以2后，其值为n，显然如果
，则
2、基于3x+1猜想的奇数体系的构建
依据上一节提出的三个定理，本节基于3x+1猜想构建一个奇数体系。
先构建一个基础数列
，令
，
，即1,5,21,85，…。不难证明，数列的通项公式为
。根据定理1可知，数列中的每一项都满足
，且只需一步运算就等于1。
从数列
的特点可知，其任意三个连续项除以3之后，余数必定是0、1、2，只是次序有所不同而已。若
，则令
，以
为首项，根据基础数列
的构建方式，构建一个新的数列；同样，若
，则令
，以
为首项，根据基础数列
的构建方式，构建一个新的数列。根据定理2、3可知，数列中的每一项都满足
，且只需一步运算就等于
。
对于新构建的数列，重复上述步骤。
这样，我们就构建了一个奇数体系，体系中的每一个数n，都符合
。模仿Collatz树的形式，上述奇数体系可以表示为如图1所示的形式。
图1 基于3x+1猜想的奇数树
Fig.1 The odd graph based of 3x+1 conjecture
对于上述奇数系或奇数树，继续证明两个问题：1，若
，则奇数n必包含于其中；2，按照上述法则构建的奇数系中不存在任意两个相等的元素，或者说，奇数树中任意两个不同位置的数不相等。
先证明第一个问题。
对于一个奇数n,若n经过一步运算就等于1，则可得等式:
,即
当k为偶数时，n属于基础数列
；当k为奇数时，容易证明n不是整数。由此可以进一步获知，式（3）中m与p的差为偶数，若
，则括号中的表达式含有因子3，可以约掉，所以为了保持表达式的唯一性，需要
。由此可知，任何一个奇数n，如果只经过一次迭代运算就得到
，则n必属于基础数列
。
基础数列中的任一元素
，若
，则可表示为
。若奇数n经过一步运算就等于
，则可得等式:
，即
根据上一步的分析可知，k必须为偶数，否则n不是整数，而最小的偶数为2。结合定理2可知，若奇数n经过一步运算就等于
，则n必属于以
为首项的数列，且
。
同样的道理，基础数列中的任一元素
，若
，则可表示为
。若奇数n经过一步运算就等于
，则可得等式:
，即
根据前述的分析可知，k必须为奇数，否则n不是整数，而最小的奇数为1。结合定理3可知，若奇数n经过一步运算就等于
，则n必属于以
为首项的数列，且
。
基础数列中的任一元素
，若
，则可表示为
。若奇数n经过一步运算就等于
，则可得等式:
，即
显然上式中的n不是整数，所以不存在这样的奇数n。据此，我们可知：对任一奇数进行迭代的过程中出现的任一元素
，满足
。
对于新得到的数列，可以采用同样的分析方法。
综上所述，可知对于任何一个奇数n，若
，则n必属于上述奇数系，即必然位于图1 所示的奇数树中。例如，经过一次运算等于1的奇数必属于数列：5，21，85，…；经过一次运算等于5的奇数必属于数列：3，13，53，…；经过一次运算等于13的奇数必属于数列：17，69，277，…；等等。
下面分析第二个问题，即同一个奇数不会出现在两个不同的数列中，或者说，奇数树中任意两个不同位置的数不相等。
首先需要说明的是：图1所示的奇数树中，除起始位置的元素为1外，不存在其它值为1 的元素。由于整个奇数体系中的每一个数列都是从一个不等于1且模3不为0的数衍生出来的。由于1经过一次迭代后其值仍为1，上述结论显然成立。
假设存在两个奇数a=b,位于奇数树上不同的位置。当对a和b进行迭代运算时，如果经过相同的迭代次数其值为1，由于运算规则相同，则每一次的迭代结果也相同，根据数列的生成和奇数树的生成过程，显然a、b不可能位于奇数树上不同的位置。如果经过不同的迭代次数其值为1，则迭代次数多的数会首先等于1，这与前述结论相矛盾。所以，上述奇数系中不会出现相同的元素，或者说，奇数树中任意两个不同位置的数不相等。
综合上述的分析，可知我们基于3x+1猜想建立了一个完备的奇数系，即对于自然数中任意一个奇数
,若n经过有限次迭代运算后等于1，即
，则n必属于该奇数系，位于图1所示的奇数树上。同时，该奇数系中的任一元素n，满足
。
根据上述论证，为便于后续分析，继续引入两个定理。
唯一性定理：对一个奇数进行迭代运算时，其每一步的结果都是唯一的。
根据算术基本定理，每个整数的素因子分解形式是唯一的，上述唯一性原理显然成立。
紧凑性定理：在奇数n和4n+1之间，不存在任何整数，其经过一次迭代后的值与n和4n+1经过一次迭代后的值相等。
根据定理1可知，奇数n和4n+1经过一次迭代运算后，其值相等，只是在迭代运算中若n除以
，则4n+1需除以
。
不妨令
，则
，
假设存在奇数m，
,经过一次迭代运算后，其值也是g,则
。对比n和4n+1的迭代值，h的取值应满足
，由于h为正整数，则
所以
，根据前述分析，由于
，m不是整数，显然紧凑性定理成立。
3、不存在其它的迭代循环或趋于无穷的情形
根据定理1、2、3，提出三个新的定理：
定理4 对于奇数n,若
，则
；反之亦然，即若
，则
。
定理5 对于奇数n,且
，若
，则
；反之亦然，即若
，则
。
定理6 对于奇数n,且
，若
，则
；反之亦然，即若
，则
。
由于定理4、5、6与定理1、2、3互为逆否命题，显然成立。
假设在自然数中存在奇数n，满足
，z是其中的最小值。利用与上一节相类似的方法，构建一个新的奇数系。
先构建一个基础数列
，令
，
。根据定理4可知，数列中的每一项都满足
。
从数列
的特点可知，其任意三个连续项除以3之后，余数必定是0、1、2，只是次序有所不同而已。若
，则令
，以
为首项，根据基础数列
的构建方式，构建一个新的数列；同样，若
，则令
，以
为首项，根据基础数列
的构建方式，构建一个新的数列。根据定理5、6可知，数列中的每一项都满足
。
对于新构建的数列，重复上述步骤。这样就构建了一个新的奇数系，如图2所示。
图2 基于最小值z的奇数树
Fig.2 The odd graph based of z
一个大于1的奇数经多次迭代后，如果不等于1，则存在两种情况：等于其自身或趋于无穷大。
假设存在大于1的奇数z，经过i次迭代后，等于其自身，则：
（4）
由上式可得：
由于z 是大于1的奇数，显然可得：
假设在图1所示的奇数系中存在两个数 x和y，y经过与式（4）相同的迭代过程后等于x，则：
（5）
由式（4）、（5）可得：
（6）
可得：
，即
（7）
同时，由式（6）可得：
（8）
由式（7）、（8）可得：
上式表明：如果存在大于1的奇数z，经过i次迭代后，等于其自身，且在图1所示的奇数系中存在两个数 x和y，y经过相同的迭代过程后等于x，则
。
下面讨论如何在图1所示的奇数系中求得 x和y。
式（5）经k-1次迭代后可得：
不妨令x取图1所示的奇数系中的基础数列，则
，只需一次迭代就等于1。根据前述分析可知，任意三个连续的
，模3的值分别为0、1、2，只是顺序有所不同。不妨令
，
的值为0、1或2。为保证方程的解为整数，根据定理1和定理3，式（5）中，若
为奇数或偶数，则可选取不同的
的值，使得
的值模3的值为2或1(若
为奇数，则选取
，使
的值模3的值为2；若
为偶数，则选取
，使
的值模3的值为1)。
根据定理（2）、（3），可得
为：
现证明上式中，任意三个连续的
的值，其模3的值必为0、1、2。
不妨设
，
根据上述两个表达式可知，若
为奇数，则：
若
为偶数，则：
。
分析以上各式，可知结论成立。
式（5）经k-2次迭代后可得：
因为
是由
经一步迭代所得，
，所以根据
为奇数或偶数，则可选取不同的
的值，使得
的值模3的值为2或1。不妨令
，
的值为0、1或2。根据定理（2）、（3），可令
为：
。同样可以证明，任意三个连续的
的值，其模3的值必为0、1、2。
上述过程假设进行到第j 步时，依然成立，则：
对于上式，需要证明任意三个连续的
的值，其模3的值必为0、1、2。
为证明上述结论，先证明如下引理：
引理1：对于任意正整数n,
为整数，且
。
当n=1时，显然成立。假设n=i时成立，讨论n=i+1时的情况。
根据假设
，可得
，其中k为自然数。对上式只需讨论
即可。
综上所述，可知引理1成立。
设
，则
。根据引理1，若
为奇数，则
；若
为偶数，则
。由此可知，任意三个连续的
的值，其模3的值必为0、1、2。因此，可以继续构造
最终，可得：
（9）
经过与式（5）相同的迭代步骤，可得
为说明上述过程，不妨设
，以此为例构造相应的y和x。
上式经一次迭代后，可得：
。根据前述分析可知，若
，则
也为正整数，根据基础数列的性质，可令
，即
，相应的可得：
上式中若i=0,
。由于4为偶数，根据相应数列的性质，可得
。根据上述公式，可得不定方程
中的x若属于图1所示奇数系中的基础数列，则其解的序列为：
根据上述分析和式（9）可知，对于任意一个式（4）所示的形式，都可以求得数列
，使得
经过相同的迭代过程后等于
，且
属于图1所示的奇数系。根据式（9）可知，随着i的增大，
将逐步增大，i趋于无穷大时，
也将趋于无穷大。但是根据式（8）可知，若式（4）成立，则
。所以满足式（4）的最小正奇数z不存在。因此可得结论：任意大于1的奇数经有限次迭代后不会等于其自身。
根据上述结论可知，图2所示的奇数系中，不存在任意两个相等的元素。假设存在两个相等的元素p、q，二者分别是由
、
衍生而得，其中
。则p、q经有限次迭代后都等于
，根据唯一性原理，如果二者的迭代次数不相等，则迭代次数多的元素的迭代过程中会出现与
相等的值，与上述结论相悖，如果迭代次数相等，则二者应该出现在相同的位置。
下面讨论是否存在大于1的奇数，经过多次迭代后趋于无穷大。假设存在这样的最小的奇数z，经过i次迭代后等于
。每一次迭代后
未必大于
，但是随着i的逐渐增大，
将趋向无穷大。则：
（10）
对上式中m和i的大小，有如下结论：对于任意有限大的正奇数迭代到一定的次数时，必存在
。
由于对一个奇数乘3加1后，必为偶数，因此迭代一次至少要除以2，即
。
任意一个正奇数n都可表示为二进制形式：
，
。由于n为奇数，显然
。下面证明：若
为上述表达式中自右起第一个为0的数，则对n迭代到第w次除以
时，其中的
。
若
，则
，结论显然成立。
若
，则可令
，
，可见经过一次乘3加1除以2的迭代运算后，迭代结果的二进制形式中
成为了表达式中自右起第一个为0的数。以此类推，可知每经过一次同样的迭代运算，第一个为0的数就向右移动一位，迭代到第w次时，
，结论成立。
若
的所有位数都为1，则
，
，显然经一次迭代后，迭代结果的二进制式中
。
综上所述，结论成立。
式（10）可改写为：
令
，则
。
显然，
、
为不定方程
的一个解。由于
，可知该方程有无穷多整数解。其解可表示为：
，其中t为整数。
由于x,y为正奇数，上式可改写为：
，其中 k为整数。
不妨假设
为不定方程
的最小正奇数解,则：
，其中 k为非负整数。
根据上述分析可知，随着迭代次数i的增加，m也不断增大。当i足够大时，
，
，上式中k只能为0。由此可知，式（10）所示的迭代过程中，当i足够大时，
、
为不定方程
的最小正奇数解。
另外，对于不定方程
，若
为方程的一组特解解，则其通解为：
，其中 k为整数。
由上式可知不定方程
必存在正整数解，不妨设
为其一组正整数解，则
为不定方程
的一组正整数解。由此可得：
由式（12）可得：
。由于z是一个固定的数，
，则
。
把k的值带入式（11），可得：
，即
。
由上述结论可得：
，即
。
但是根据
、
为不定方程
的一个解，可得
，由于z是一个固定的正奇数，显然
。上述结论相互矛盾的，由此可知：不存在大于1的奇数，经过多次迭代后趋于无穷大。
根据上述分析可知，任意大于1的奇数经有限次迭代后不会等于其自身，也不会趋于无穷大，即图2所示的奇数系是不存在的。进而可知3x+1猜想是正确的。
5、进一步的讨论
根据上述的讨论可知，我们建立了一个完备的奇数体系，且对于任一奇数，
，满足
。数的体系有不同的表达方式，诸如二进制、十进制、六十进制、罗马数系等等，每种数系展现不同的特点。用本文的方法建立的数系能够顺利地解释3x+1猜想。
在对3x+1猜想进行讨论时，人们往往会考虑是否存在迭代的最小停止次数K和最小上界M，即对任意自然数进行迭代运算时，最多K次就等于1，迭代过程中出现的值都不大于M。这样的K和M是不存在的。
假设存在这样的K和M，令
，其迭代过程为：
从上式可以看出，只要令
，则n的停止次数大于K、迭代过程中出现的值大于M。
基于3x+1猜想，人们进而会考虑nx+1问题，比如5x+1或7x+1问题。对于这样的问题可以采用同样的方法进行分析。以5x+1或7x+1问题为例，可以用以下形式表示奇数：
对于前者可以用
的模式产生数列，后者可以用
的模式产生数列，具体细节有待进一步的分析。
本文中曾假设存在不符合3x+1猜想的最小的正奇数z，然后根据相应的规则构建了图2所示的奇数系。比较图1、图2两个不同的奇数系，如果采用解析数论等方法，在自然密度意义上进行分析，可能会得出更有意义的结论。
参 考 文 献 ：
[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. 关于（3n+1）问题的起因[J]，任志平，译。曲阜师范大学学报（自然科学版），1986（3）：9~11.
[6] CHEN Tieling．Discoveries on Collatz Conjecture．Journal of Qufu Normal University, Jan.2020, Vol. 46 No.1:11~18.
基于3x+1猜想的奇数体系构建及证明