Collatz 二進(jìn)制序列的算法與停時(shí)＊

許道云 ，代寸寬

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽550025)

德國數(shù)學(xué)家洛薩·科拉茨(Lothar Collatz)于1937 年提出一個(gè)著名猜想(稱為Collaze 問題):任給一個(gè)正整數(shù)，如果是偶數(shù)，就將它減半(n/2);如果它是奇數(shù)，則將它乘3 加1(3n +1)。不斷重復(fù)這樣的運(yùn)算，經(jīng)過有限步后，一定可以得到1。盡管Collaze 問題的描述簡單，但至今沒有證明對所有的正整數(shù)該過程都能有限終止。有關(guān)該問題的介紹和各種方法的試探可以參見文獻(xiàn)［1 -12］。

例，對于初值7，經(jīng)過16 步計(jì)算后得到1，并生成如下有限Collatz 序列:

7，22，11，34，17，52，26，13，40，20，10，5，16，8，4，2，1。

如果忽略出現(xiàn)在序列中的偶數(shù)，則得到:7，11，17，13，5，1。反之，通過7，11，17，13，5，1 可以恢復(fù)原始Collatz 序列。可以看出:Collaze 序列能否有限終止，取決于序列中的奇數(shù)部分。

為此，只考慮序列中的奇數(shù)部分。在本文中，利用二進(jìn)制方法給出了一個(gè)序列生成算法，稱為Collatz_Binary 算法。將Collatz 序列的計(jì)算轉(zhuǎn)變?yōu)榉栠\(yùn)算，這對大整數(shù)計(jì)算是有效的。進(jìn)一步，引入串運(yùn)算下的停時(shí)概念，從數(shù)學(xué)歸納法的角度來說，如果在有限步內(nèi)可以得到比初始串長度更短的串，則初始串可以在有限步內(nèi)計(jì)算可終止。

基于Collatz_Binary 算法，實(shí)驗(yàn)觀察二進(jìn)制奇數(shù)收斂到1 的最大迭代步數(shù)與長度的關(guān)系。在做了大量實(shí)驗(yàn)后，給出了長度從3 到37 二進(jìn)制串的最大收斂步數(shù)與長度的關(guān)系?？梢杂^察到:在長度從3 到37 之間，最大迭代步數(shù)與長度之間幾乎是線性關(guān)系。因此猜測:最大迭代步數(shù)受長度的一個(gè)線性函數(shù)控制。如果這個(gè)猜測成立，則對任意長(二進(jìn)制串的長度)的數(shù)，收斂步數(shù)有限。

1 Collatz 問題的串序列算法

本節(jié)給出Collatz 序列生成的二進(jìn)制串序列算法。將Collatz 序列的計(jì)算轉(zhuǎn)變?yōu)榉栠\(yùn)算，停機(jī)問題變?yōu)闇y試是否能得到串‘1’。

Collatz-Binary 算法:

(1)輸入一個(gè)正整數(shù)n;

(2)將n 化為二進(jìn)制串S=a1，a2，……，ak，其中a1=1，S 為初始串;

(3)如果S 的后綴含有純0 子串，則S←從S的后綴中刪去純0 子串;

(4)如果|S| =1，則輸出1，并終止算法;否則進(jìn)入(5);

(5)S←0S + S0(將0S，S0 作二進(jìn)制加法運(yùn)算，運(yùn)算結(jié)果賦給S);

(6)如果S 不含符號0，則S←1，然后轉(zhuǎn)入(4);否則進(jìn)入(7);

(7)S←將S 后綴中形如01m(m≥1)的子串用1 取代;然后轉(zhuǎn)入(4);

算法流程圖如圖1 所示:

圖1 Collatz-Binary 算法流程圖

算法的正確性說明:

一個(gè)正整數(shù)n 的二進(jìn)制表示的0/1 串中，確保首位為1。

(1)如果n 為偶數(shù)，則n 可以表示為n =n'2m(m≥1)，其中n'為奇數(shù)。則從n 的二進(jìn)制串中直接刪去純0 后綴子串后得到n'的二進(jìn)制串。這相當(dāng)于連續(xù)對偶數(shù)進(jìn)行處理。

(2)如果n 為奇數(shù)，n 的二進(jìn)制串為S，則3n必為奇數(shù)，且3n 二進(jìn)制串直接由0S +S0 得到(這里的加法為二進(jìn)制加法)?？梢钥闯?0S +S0 的首位和末位必為1。

因此，如果0S+S0 中不含0(即為純1 串)，則3n+1 必有形式2k(k≥4)。此時(shí)可認(rèn)為計(jì)算可終止。如果0S +S0 中含0，則其二進(jìn)制串必有01m(m≥1)后綴子串，于是3n +1 的二進(jìn)制串必有10m(m≥1)后綴子串。對此，在算法中直接用“1”替換01m。它對應(yīng)Collatz 序列中n 的下一個(gè)奇數(shù)。這里1m表示m 個(gè)1 形成的號串。

因此，在算法中，重點(diǎn)是對奇數(shù)進(jìn)行處理，忽略偶數(shù)情形。

例如:對于n =7，其二進(jìn)制串為111。算法執(zhí)行過程生成的串序列為:

算法的優(yōu)點(diǎn)在于:縮短了Collatz 序列，給有限終止分析帶來了方便。如:以7 開頭的原始Collatz序列長度為17。在串法下，其長度壓縮為6。

2 串停時(shí)與最大停時(shí)現(xiàn)象

對于Collatz 問題的研究，“停時(shí)”是一個(gè)重要概念。直觀上，經(jīng)過k 步運(yùn)算后，首次得到比初始數(shù)n 更小的數(shù)，則k 稱為n 的停時(shí)。R. Terras 給出了一個(gè)“停時(shí)”函數(shù)χ:N→N 的定義［4］:

并研究Collaze 序列的停時(shí)現(xiàn)象和分布。在此定義下，χ(0)= χ(1)= ∞，對此平凡現(xiàn)象不作考慮。

基于串長度的變化，引入了串“停時(shí)”的概念。

記∑odd表示首位和末位均為1 的0、1 有窮符號串集合，它與正奇數(shù)集一一對應(yīng)。為長度為n，且首位和末位均為1 的0、1 符號串集合。如:{101，111}，……。

定義一個(gè)運(yùn)算Tb:∑odd→∑odd，對于S ∈∑odd，Tb(S)定義為:

如:Tb(1)= 1，Tb(101)= 1，Tb(111101)=10111，Tb(100011)= 110101。

利用串長度的縮短引入串停時(shí)函數(shù)

則 χb(S):=

可以驗(yàn)證:

實(shí)驗(yàn)中發(fā)現(xiàn)，當(dāng)串長度不超過37 時(shí)，最大停時(shí)受串長的某個(gè)線性函數(shù)所界。

圖2 與的關(guān)系

對于固定長度的串，含0 位的個(gè)數(shù)與0 位的分布與停時(shí)有很大關(guān)系。但是，對于固定的含0 位數(shù)，當(dāng)串的長度增大時(shí)，并非含0 位越多停時(shí)就越小。如下通過幾組實(shí)驗(yàn)可以觀察這一現(xiàn)象。

對于固定長度的串，通過逐步增加0 位出現(xiàn)，觀察最大停時(shí)的變化趨勢。

圖3 不含0 位串的停時(shí)與含1 個(gè)0 位串的最大停時(shí)對比(固定長度從5 到300)

從圖3 可以看出，對于固定長度的串，極大多數(shù)含有1 位0 位串的最大停時(shí)大于不含0 位串的停時(shí)。

下面的實(shí)驗(yàn)結(jié)果說明:0 位所在串中的位置影響停時(shí)。

圖4 含1 個(gè)、2 個(gè)、3 個(gè)0 位串的對位停時(shí)對比

從圖4 可以看出，對于固定長度為N =150 的串，從第3 位到第N-2 位，極大多數(shù)含多0 位的最大停時(shí)大于含較少數(shù)0 位的最大停時(shí)。圖4 還說明，0 位靠近前端的停時(shí)大于靠近后端的停時(shí)。

3 收縮與膨脹

本節(jié)引入收縮與膨脹的概念，用來描述在Collatz-Binary 算法下下一個(gè)位串的長度與上一個(gè)位串長度之間的關(guān)系。收縮指下一個(gè)位串的長度比上一個(gè)位串的長度短，膨脹指下一個(gè)位串的長度比上一個(gè)位串的長度長。對于S ∈∑odd，引入如下函數(shù):

記錄后綴純1 子綴長度。

Expand(S):=| 0S +S0| -| S|，記錄0S +S0比S 增加的位數(shù)。容易驗(yàn)證，

Lk(S)的直觀含義是，S 在Collatz-Binary 算法下的下一個(gè)位串的長度比S 的長度減少的值。

例如，對于k =5，上述函數(shù)取值見表1。

表1 上Ones(S)、Expand(S)和Lk(S)的取值

表1 上Ones(S)、Expand(S)和Lk(S)的取值

十進(jìn)制數(shù) S Ones(S)Expand(S) Lk(S) |Tb(S)| Tb(S)17 10001 2 1 1 4 1101 19 10011 1 1 0 5 11101 21 10101 6 1 5 1 1 23 10111 1 2 -1 6 100011 25 11001 2 2 0 5 10011 27 11011 1 2 -1 6 101001 29 11101 3 2 1 4 1011 31 11111 1 2 -1 6 101111

當(dāng)Lk(S)＞0 時(shí)，χb(S)= 1 。以作為例子，用自動機(jī)來刻畫S 的倒數(shù)第二位與停時(shí)的關(guān)系如下:

圖5 倒數(shù)第二位與停時(shí)的關(guān)系

其中，Stop 表示χb(S)= 1，即S 經(jīng)過一步將收縮到比| S| 短的位串;Next 表示S 經(jīng)過一步將膨脹成| S| +1 位。邊上的數(shù)字是S 的倒數(shù)第二位的取值，如表示10001 經(jīng)過一步將“收縮”。由圖5 可看出，對任意的x ∈，經(jīng)過一步將收縮的概率為3/8，經(jīng)過一步仍停留在中概率為2/8，經(jīng)過一步將膨脹成6 位的概率為3/8。

(1)S 以100 開頭，以01 結(jié)尾;

(2)S 以(10)*11 開頭，以101 結(jié)尾;

(3)S = (10)+1 。證明 (?)由χb(S)= 1 可得| Tb(S)| ＜| S| ，從而Expand(S)＜Ones(S)。Expand(S)的值只有1 和2 兩種。Expand(S)= 1 ，則Ones(S)≥2 ;Expand(S)= 2 ，則Ones(S)≥3 。使Expand(S)= 1，Ones(S)= 2 成立的唯一條件是S 以100 開頭，以01 結(jié)尾，即條件(1)。使Expand(S)= 1，Ones(S)＞2 成立的唯一條件是S = (10)+1 ，即條件(3)。使Expand(S)=2，Ones(S)≥3 成立的唯一條件是S 以(10)*11 開頭，以101 結(jié)尾，即條件(2)。

(?)(1)當(dāng)S 以100 開頭，以01 結(jié)尾時(shí)，設(shè)S= 100S'01 ，0S + S0 的二進(jìn)制加法如下(第3 行為第1、2 相加的結(jié)果)

此時(shí)Lk(S)=Ones(S)-Expand(S)≥2 -1 ＞0，χb(S)= 1 。

(2)當(dāng)S 以(10)*11 開頭，以101 結(jié)尾時(shí)，設(shè)S= 1011S'101 ，0S + S0 的二進(jìn)制加法為

其中0S' +S'0 = 0S″，| S″| =| S'| +1 ，最高位無進(jìn)位，或

其中0S' +S'0 = 1S″，| S″| =| S'| +1 ，最高位有進(jìn)位。

無論哪種情形，Expand(S)=2，Ones(S)≥3，Lk(S)= Ones(S)- Expand(S)≥3 - 2 ＞0 ，χb(S)= 1 。

(3)當(dāng)S = (10)*1 時(shí)，0S + S0 為全1 的串，Tb(S)= 1 ，χb(S)= 1 。

(a)k 為奇數(shù)。以(10)*11 開頭，以101 結(jié)尾的串的個(gè)數(shù)為

(b)k 為偶數(shù)。以(10)*11 開頭，以101 結(jié)尾的串的個(gè)數(shù)(首串和尾串可以共用1 個(gè)“1”)為

下面證明S 經(jīng)過一步將膨脹的概率?？疾鞚M足引理2 中條件的位串個(gè)數(shù)，除以2k-2即可。分3種情況討論:

k 為奇數(shù)時(shí)，首串和尾串可以共用1 個(gè)“1”，k為偶數(shù)時(shí)，首串和尾串可以共用2 個(gè)“1”。

S 經(jīng)過一步將膨脹的概率為

盡管S 經(jīng)過一步能收縮的概率不算高，實(shí)驗(yàn)表明，S 在m(m ＞1)步內(nèi)能收縮的概率將大大增加。由于這種情況下的理論研究比較復(fù)雜。

4 結(jié)語

Collatz 問題提出以來，吸引了眾多數(shù)學(xué)愛好者和數(shù)學(xué)家進(jìn)行一些試探性研究。同時(shí)也誘發(fā)一些有意思的問題和方法，但較深刻的結(jié)果和突破性的結(jié)論并不多見。本文給出的串表示算法只是一種嘗試，實(shí)驗(yàn)觀察的目的是想對串滿足一定分類條件下的停時(shí)現(xiàn)象。經(jīng)驗(yàn)證，當(dāng)串長度在300 以內(nèi)時(shí)，Collatz 猜想是正確的。在圖2 中，給出了長度從3到37 二進(jìn)制串的最大收斂步數(shù)與長度的關(guān)系?？梢杂^察到:最大迭代步數(shù)與長度之間幾乎是線性關(guān)系。因此猜測:最大迭代步數(shù)受長度的一個(gè)線性函數(shù)控制。如果這個(gè)猜測成立，則對任意長(二進(jìn)制串的長度)的數(shù)，收斂步數(shù)有限。

［1］Wikipedia. Collatz conjecture［EB/OL］.［2015 - 07 - 10］. https://en.wikipedia.org/wiki/Collatz_conjecture.

［2］C L Jeffrey.The 3x+1 problem and its generalizations［J］.The American Mathematical Monthly，1985，92(1):3 -23.

［3］J Sinyor.The 3x+1 Problem as a String Rewriting System［J］. International Journal of Mathematics and Mathematical Sciences，2010:458563 -458563 -6.

［4］R Terras.A stopping time problem on the positive integers［J］.Polska Akademia Nauk，1976，30(3):241 -252.

［5］J Simons，B de Weger.Theoretical and computational bounds for mcycles of the 3n+1 problem［J］.Acta Arithmetica(on-line version 1.0，November 18，2003)，2005，117(1):51 -70.

［6］J O Shallit.The 3x+1 problem and finite automata［J］.Bulletin of the AETCS，1992，46:182 -185.

［7］M Chamberland. A continuous extension of the 3x +1 problem to the real line［J］. Dynam Contin Discrete Impuls Systems，1996，4(2):495 -509.

［8］I Krasikov，C L.Jeffrey. Bounds for the 3x+1 problem using difference inequalities［J］.Acta Arithmetica，2003，109(3):237 -258.

［9］K Hicks，G L Mullen，J L Yucas，et al. A Polynomial Analogue of the 3N+1 Problem［J］.American Math. Monthly，2008，115(7):615 -622.

［10］B Kraft，K Monks. On conjugacies of the 3x +1 map induced by continuous endomorphisms of the shift dynamical system［J］.Discrete Mathematics，2010，310(13 -14):1875 -1883.

［11］WANG Xing-yuan，YU Xue-jing. Dynamics of the generalized 3x+1 function determined by its fractal images［J］.Progress in Natural Science，2008，18(2):217 -223.

［12］G Scollo. Looking for Class Records in the 3x + 1 Problem by means of the COMETA Grid Infrastructure［C］//Proc Symp Grid Open Days at the University of Palermo，Palermo (Italy)，6 -7 December 2007，Catania:Consorzio COMETA，2008:255 -263.