用四进制数研究3X+1 猜想

吴文良，姜 娜，何佳颖，周杨川

（昭通学院物理与信息工程学院，云南昭通 657000）

Guy 在文献〔1〕中介绍了3X+1 问题：对于迭代

是否从任何一个正整数a1开始，都有一个n 使得an＝1？对这个问题作“是”的回答，就是著名的3X+1猜想。

自20 世纪3X+1 猜想提出以来，相关研究论著浩如烟海〔1-6〕，不仅有了3N+1 猜想、角谷猜想、Collatz 猜想、奇偶归一猜想、冰雹猜想（大雪崩猜想）、Syracuse 猜想等诸多让人眼花缭乱的别称，而且有不少文章宣称证明了这一猜想〔7-9〕。在文献〔10〕用五进制和三进制数研究该猜想的基础上，从四进制数角度来探索这一猜想，得到了一些有趣的结果。

1 约定

文献〔2〕基于如下事实提出压缩迭代：若所有奇数符合3X+1 猜想，则所有正整数也符合3X+1 猜想。所谓压缩迭代，是指：

式中e（an）是使偶数3an+1 能被2e（an）整除的最大自然数〔2〕。

为使行文简便，文章约定用m 表示正整数，n

约定用a（b）表示a 是b 进位制数。约定用方括号表示括号内的内容可有可无，而圆括号内的内容则是必须有的四进制数序列，例如：

式中E（x）表示x 的高斯取整函数。其余类推。为避免混淆，文中一律不省略乘号。

一个n 位b 进制数，本质上是一个用来描述某个自然数的n 维向量，它的第i 个分量是它的bi-1位，它的每个分量都是小于b 的自然数，它的第n个分量则是小于b 的正整数，而它所表示的自然数，就是它和n 维向量（1，b，b2，…，bn-1）的内积。把它的各个分量自右往左书写，便成为这个自然数的b 进位制表示。如果允许它的最高位为0，则称其为广义的n 位b 进制数。

人们习惯上使用的进位制为十进位制，计算机语言采用的则是二进位制，而在计量时间或者角度时人们又在某个范围内采用六十进位制。为了便于阅读计算机的语言，人们也常采用八进位制和十六进位制。用四进位制研究3X+1 猜想，或许是一种更好的选择。

除了0 乘任何数得0 外，四进位制的乘法共有9 句口诀，由乘法的交换律只需记住其中的6 句。再去掉1 乘任何数得任何数，实际上只需要记住如下3句即可：2×2=10（4），2×3=12（4），3×3=21（4），这是本文计算的基础。

2 阶数为1 或2 的奇数

问：什么样的奇数经过1 次迭代落入a1（m+1）？

一个奇数b 经过1 次迭代落入a1（m+1），有且只有以下两种情形：

从上式可见，有两类奇数的阶数为2：第一类（013）0（1）由词根1301（4）加上前缀［130］和后缀［1］构成。其中最小的是1301（4）=113（10），接下来较小的前几个是13011（4）=453（10），130111（4）=1813（10），1301111（4）=7253（10），1301301（4）=7281（10），13013011（4）=29125（10）。第二类［032］03［1］，由词根3 加上前缀［320］和后缀［1］构成，最小的是3，接下来的几个是31（4）=13（10），311（4）=53（10），3111（4）=213（10），3203（4）=227（10），32031（4）=909（10）。

3 阶数为3 的奇数

什么样的奇数能够经过1 次变换后落入b1或者b2？

奇数c 经过1 次变换后落入b1，有如下一些情形：

奇数c 经过1 次变换后落入b2，则相应情形如下：

解得：

可见，c33和c34可以合并表示为：

可见，经3 次变换后落入不动点1 的奇数可分为13 类，见表1。

表1 阶数为3 的奇数分类

4 四阶奇数举例

对于四阶奇数，为简洁起见，将序列［002113231］简记为［a3（1）］，［010233122］简记为［2×a3（1）］，［000302210112013321223131033］简记为［a4（1）］，其余类推。作为一个特例，下面分析有哪些奇数经过1 次迭代能成为三阶奇数［021132310］0［203］［1］。

这些奇数可分为如下3 种情形：

第一种情形的奇数是四进制数［021132310］0［203］202（3）的1/3，有以下3 类：

12（1）。

第二种情形的奇数是四进制数［021132310］0（203）［1］0（3）的1/3，有以下9 类：（1）］1223［013］0（1），

d28=［a4（1）］000302210112013321223［23（4）×a3（1）］12201［013］0（1），

d29=［a4（1）］000302210112013321223［23（4）×a3（1）］122010233［013］0（1）。

第三种情形的奇数则是四进制数［102331220］1［013］01［2］1［3］的1/3，有以下9 类：

d31=［2×a4（1）］001［31（4）×a3（1）］1［320］3［1］，

d32=［2×a4（1）］0011323［13（4）×a3（1）］［032］03［1］，

d33=［2×a4（1）］00113231［a3（1）］002［032］03［1］，

d34=［2×a4（1）］0121102023［a3（1）］002［032］03［1］，

d35=［2×a4（1）］0121102023［a3（1）］00211［320］3［1］，

d36=［2×a4（1）］0121102023［a3（1）］00211323［032］03［1］，

d37=［2×a4（1）］01211020230033031123［13（4）×a3（1）］［032］03［1］，

d38=［2×a4（1）］012110202300330311231［a3（1）］002［032］03［1］，

d39=［2×a4（1）］012110202300330311231［a3（1）］00211［320］3［1］。

注意到d11和d23可合并为［a4（1）］00［11（4）×a3（1）］023312［130］（1）；d12和d26可合并为［a4（1）］000302210112［2×a3（1）］01023312［130］（1）；d13和d27可合并为［a4（1）］000302210112013321223［23（4）×a3（1）］12［130］（1），实际上经过1 次迭代能成为三阶奇数［021132310］0（203）［1］的奇数共有18 类。

5 推论

“管中窥豹，可见一斑”。从前面的推导过程可见，任意阶次奇数的四进制表示均可化分为前缀、词根和后缀3 个部分。本级的前缀决定了高一级次的前缀，本级的后缀通常是更低级次的奇数。本级的词根则由低一级次的前缀、词根和后缀共同决定。特别地，一阶奇数的四进制表示，其词根为1，前缀和后缀也均是若干个1。

这个新的循环序列或其2 倍的四进制表示，即为相应阶次奇数的前缀。前面几个的am（1）为：

设m 级奇数的词根数目为k（m），则

这是因为奇数的四进制表示中的参数个数t（即不同循环序列的个数）等于该奇数的阶次；这些序列对3 模为0 的组合，则有3t-1种不同可能。较小的几个k（m）为k（1）=1，k（2）=2，k（3）=12。随着级次的增加，词根数目迅速增长。

如此得到一棵根深枝繁叶茂的参天大树，见图1。是否存在某个奇数不出现在这棵大树上，就成为3X+1 问题的另一种表述方式。而确定四阶及以上某一阶奇数的所有词根，或许是一件有趣而繁难的工作。通过以上讨论，又一次见证一个简单的数学问题，其逆问题与原问题相比较往往非常困难。

图1 3X+1 猜想逆问题树