用四進制數(shù)研究3X+1 猜想

吳文良，姜 娜，何佳穎，周楊川

（昭通學(xué)院物理與信息工程學(xué)院，云南昭通 657000）

Guy 在文獻〔1〕中介紹了3X+1 問題：對于迭代

是否從任何一個正整數(shù)a1開始，都有一個n 使得an＝1？對這個問題作“是”的回答，就是著名的3X+1猜想。

自20 世紀3X+1 猜想提出以來，相關(guān)研究論著浩如煙?！?-6〕，不僅有了3N+1 猜想、角谷猜想、Collatz 猜想、奇偶歸一猜想、冰雹猜想（大雪崩猜想）、Syracuse 猜想等諸多讓人眼花繚亂的別稱，而且有不少文章宣稱證明了這一猜想〔7-9〕。在文獻〔10〕用五進制和三進制數(shù)研究該猜想的基礎(chǔ)上，從四進制數(shù)角度來探索這一猜想，得到了一些有趣的結(jié)果。

1 約定

文獻〔2〕基于如下事實提出壓縮迭代：若所有奇數(shù)符合3X+1 猜想，則所有正整數(shù)也符合3X+1 猜想。所謂壓縮迭代，是指：

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

為使行文簡便，文章約定用m 表示正整數(shù)，n

約定用a（b）表示a 是b 進位制數(shù)。約定用方括號表示括號內(nèi)的內(nèi)容可有可無，而圓括號內(nèi)的內(nèi)容則是必須有的四進制數(shù)序列，例如：

式中E（x）表示x 的高斯取整函數(shù)。其余類推。為避免混淆，文中一律不省略乘號。

一個n 位b 進制數(shù)，本質(zhì)上是一個用來描述某個自然數(shù)的n 維向量，它的第i 個分量是它的bi-1位，它的每個分量都是小于b 的自然數(shù)，它的第n個分量則是小于b 的正整數(shù)，而它所表示的自然數(shù)，就是它和n 維向量（1，b，b2，…，bn-1）的內(nèi)積。把它的各個分量自右往左書寫，便成為這個自然數(shù)的b 進位制表示。如果允許它的最高位為0，則稱其為廣義的n 位b 進制數(shù)。

人們習(xí)慣上使用的進位制為十進位制，計算機語言采用的則是二進位制，而在計量時間或者角度時人們又在某個范圍內(nèi)采用六十進位制。為了便于閱讀計算機的語言，人們也常采用八進位制和十六進位制。用四進位制研究3X+1 猜想，或許是一種更好的選擇。

除了0 乘任何數(shù)得0 外，四進位制的乘法共有9 句口訣，由乘法的交換律只需記住其中的6 句。再去掉1 乘任何數(shù)得任何數(shù)，實際上只需要記住如下3句即可：2×2=10（4），2×3=12（4），3×3=21（4），這是本文計算的基礎(chǔ)。

2 階數(shù)為1 或2 的奇數(shù)

問：什么樣的奇數(shù)經(jīng)過1 次迭代落入a1（m+1）？

一個奇數(shù)b 經(jīng)過1 次迭代落入a1（m+1），有且只有以下兩種情形：

從上式可見，有兩類奇數(shù)的階數(shù)為2：第一類（013）0（1）由詞根1301（4）加上前綴［130］和后綴［1］構(gòu)成。其中最小的是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］構(gòu)成，最小的是3，接下來的幾個是31（4）=13（10），311（4）=53（10），3111（4）=213（10），3203（4）=227（10），32031（4）=909（10）。

3 階數(shù)為3 的奇數(shù)

什么樣的奇數(shù)能夠經(jīng)過1 次變換后落入b1或者b2？

奇數(shù)c 經(jīng)過1 次變換后落入b1，有如下一些情形：

奇數(shù)c 經(jīng)過1 次變換后落入b2，則相應(yīng)情形如下：

解得：

可見，c33和c34可以合并表示為：

可見，經(jīng)3 次變換后落入不動點1 的奇數(shù)可分為13 類，見表1。

表1 階數(shù)為3 的奇數(shù)分類

4 四階奇數(shù)舉例

對于四階奇數(shù)，為簡潔起見，將序列［002113231］簡記為［a3（1）］，［010233122］簡記為［2×a3（1）］，［000302210112013321223131033］簡記為［a4（1）］，其余類推。作為一個特例，下面分析有哪些奇數(shù)經(jīng)過1 次迭代能成為三階奇數(shù)［021132310］0［203］［1］。

這些奇數(shù)可分為如下3 種情形：

第一種情形的奇數(shù)是四進制數(shù)［021132310］0［203］202（3）的1/3，有以下3 類：

12（1）。

第二種情形的奇數(shù)是四進制數(shù)［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）。

第三種情形的奇數(shù)則是四進制數(shù)［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），實際上經(jīng)過1 次迭代能成為三階奇數(shù)［021132310］0（203）［1］的奇數(shù)共有18 類。

5 推論

“管中窺豹，可見一斑”。從前面的推導(dǎo)過程可見，任意階次奇數(shù)的四進制表示均可化分為前綴、詞根和后綴3 個部分。本級的前綴決定了高一級次的前綴，本級的后綴通常是更低級次的奇數(shù)。本級的詞根則由低一級次的前綴、詞根和后綴共同決定。特別地，一階奇數(shù)的四進制表示，其詞根為1，前綴和后綴也均是若干個1。

這個新的循環(huán)序列或其2 倍的四進制表示，即為相應(yīng)階次奇數(shù)的前綴。前面幾個的am（1）為：

設(shè)m 級奇數(shù)的詞根數(shù)目為k（m），則

這是因為奇數(shù)的四進制表示中的參數(shù)個數(shù)t（即不同循環(huán)序列的個數(shù)）等于該奇數(shù)的階次；這些序列對3 模為0 的組合，則有3t-1種不同可能。較小的幾個k（m）為k（1）=1，k（2）=2，k（3）=12。隨著級次的增加，詞根數(shù)目迅速增長。

如此得到一棵根深枝繁葉茂的參天大樹，見圖1。是否存在某個奇數(shù)不出現(xiàn)在這棵大樹上，就成為3X+1 問題的另一種表述方式。而確定四階及以上某一階奇數(shù)的所有詞根，或許是一件有趣而繁難的工作。通過以上討論，又一次見證一個簡單的數(shù)學(xué)問題，其逆問題與原問題相比較往往非常困難。

圖1 3X+1 猜想逆問題樹