Collatz 二进制序列的算法与停时＊

许道云 ，代寸宽

(贵州大学 计算机科学与技术学院，贵州 贵阳550025)

德国数学家洛萨·科拉茨(Lothar Collatz)于1937 年提出一个著名猜想(称为Collaze 问题):任给一个正整数，如果是偶数，就将它减半(n/2);如果它是奇数，则将它乘3 加1(3n +1)。不断重复这样的运算，经过有限步后，一定可以得到1。尽管Collaze 问题的描述简单，但至今没有证明对所有的正整数该过程都能有限终止。有关该问题的介绍和各种方法的试探可以参见文献［1 -12］。

例，对于初值7，经过16 步计算后得到1，并生成如下有限Collatz 序列:

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

如果忽略出现在序列中的偶数，则得到:7，11，17，13，5，1。反之，通过7，11，17，13，5，1 可以恢复原始Collatz 序列。可以看出:Collaze 序列能否有限终止，取决于序列中的奇数部分。

为此，只考虑序列中的奇数部分。在本文中，利用二进制方法给出了一个序列生成算法，称为Collatz_Binary 算法。将Collatz 序列的计算转变为符号运算，这对大整数计算是有效的。进一步，引入串运算下的停时概念，从数学归纳法的角度来说，如果在有限步内可以得到比初始串长度更短的串，则初始串可以在有限步内计算可终止。

基于Collatz_Binary 算法，实验观察二进制奇数收敛到1 的最大迭代步数与长度的关系。在做了大量实验后，给出了长度从3 到37 二进制串的最大收敛步数与长度的关系。可以观察到:在长度从3 到37 之间，最大迭代步数与长度之间几乎是线性关系。因此猜测:最大迭代步数受长度的一个线性函数控制。如果这个猜测成立，则对任意长(二进制串的长度)的数，收敛步数有限。

1 Collatz 问题的串序列算法

本节给出Collatz 序列生成的二进制串序列算法。将Collatz 序列的计算转变为符号运算，停机问题变为测试是否能得到串‘1’。

Collatz-Binary 算法:

(1)输入一个正整数n;

(2)将n 化为二进制串S=a1，a2，……，ak，其中a1=1，S 为初始串;

(3)如果S 的后缀含有纯0 子串，则S←从S的后缀中删去纯0 子串;

(4)如果|S| =1，则输出1，并终止算法;否则进入(5);

(5)S←0S + S0(将0S，S0 作二进制加法运算，运算结果赋给S);

(6)如果S 不含符号0，则S←1，然后转入(4);否则进入(7);

(7)S←将S 后缀中形如01m(m≥1)的子串用1 取代;然后转入(4);

算法流程图如图1 所示:

图1 Collatz-Binary 算法流程图

算法的正确性说明:

一个正整数n 的二进制表示的0/1 串中，确保首位为1。

(1)如果n 为偶数，则n 可以表示为n =n'2m(m≥1)，其中n'为奇数。则从n 的二进制串中直接删去纯0 后缀子串后得到n'的二进制串。这相当于连续对偶数进行处理。

(2)如果n 为奇数，n 的二进制串为S，则3n必为奇数，且3n 二进制串直接由0S +S0 得到(这里的加法为二进制加法)。可以看出:0S +S0 的首位和末位必为1。

因此，如果0S+S0 中不含0(即为纯1 串)，则3n+1 必有形式2k(k≥4)。此时可认为计算可终止。如果0S +S0 中含0，则其二进制串必有01m(m≥1)后缀子串，于是3n +1 的二进制串必有10m(m≥1)后缀子串。对此，在算法中直接用“1”替换01m。它对应Collatz 序列中n 的下一个奇数。这里1m表示m 个1 形成的号串。

因此，在算法中，重点是对奇数进行处理，忽略偶数情形。

例如:对于n =7，其二进制串为111。算法执行过程生成的串序列为:

算法的优点在于:缩短了Collatz 序列，给有限终止分析带来了方便。如:以7 开头的原始Collatz序列长度为17。在串法下，其长度压缩为6。

2 串停时与最大停时现象

对于Collatz 问题的研究，“停时”是一个重要概念。直观上，经过k 步运算后，首次得到比初始数n 更小的数，则k 称为n 的停时。R. Terras 给出了一个“停时”函数χ:N→N 的定义［4］:

并研究Collaze 序列的停时现象和分布。在此定义下，χ(0)= χ(1)= ∞，对此平凡现象不作考虑。

基于串长度的变化，引入了串“停时”的概念。

记∑odd表示首位和末位均为1 的0、1 有穷符号串集合，它与正奇数集一一对应。为长度为n，且首位和末位均为1 的0、1 符号串集合。如:{101，111}，……。

定义一个运算Tb:∑odd→∑odd，对于S ∈∑odd，Tb(S)定义为:

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

利用串长度的缩短引入串停时函数

则 χb(S):=

可以验证:

实验中发现，当串长度不超过37 时，最大停时受串长的某个线性函数所界。

图2 与的关系

对于固定长度的串，含0 位的个数与0 位的分布与停时有很大关系。但是，对于固定的含0 位数，当串的长度增大时，并非含0 位越多停时就越小。如下通过几组实验可以观察这一现象。

对于固定长度的串，通过逐步增加0 位出现，观察最大停时的变化趋势。

图3 不含0 位串的停时与含1 个0 位串的最大停时对比(固定长度从5 到300)

从图3 可以看出，对于固定长度的串，极大多数含有1 位0 位串的最大停时大于不含0 位串的停时。

下面的实验结果说明:0 位所在串中的位置影响停时。

图4 含1 个、2 个、3 个0 位串的对位停时对比

从图4 可以看出，对于固定长度为N =150 的串，从第3 位到第N-2 位，极大多数含多0 位的最大停时大于含较少数0 位的最大停时。图4 还说明，0 位靠近前端的停时大于靠近后端的停时。

3 收缩与膨胀

本节引入收缩与膨胀的概念，用来描述在Collatz-Binary 算法下下一个位串的长度与上一个位串长度之间的关系。收缩指下一个位串的长度比上一个位串的长度短，膨胀指下一个位串的长度比上一个位串的长度长。对于S ∈∑odd，引入如下函数:

记录后缀纯1 子缀长度。

Expand(S):=| 0S +S0| -| S|，记录0S +S0比S 增加的位数。容易验证，

Lk(S)的直观含义是，S 在Collatz-Binary 算法下的下一个位串的长度比S 的长度减少的值。

例如，对于k =5，上述函数取值见表1。

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

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

十进制数 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

当Lk(S)＞0 时，χb(S)= 1 。以作为例子，用自动机来刻画S 的倒数第二位与停时的关系如下:

图5 倒数第二位与停时的关系

其中，Stop 表示χb(S)= 1，即S 经过一步将收缩到比| S| 短的位串;Next 表示S 经过一步将膨胀成| S| +1 位。边上的数字是S 的倒数第二位的取值，如表示10001 经过一步将“收缩”。由图5 可看出，对任意的x ∈，经过一步将收缩的概率为3/8，经过一步仍停留在中概率为2/8，经过一步将膨胀成6 位的概率为3/8。

(1)S 以100 开头，以01 结尾;

(2)S 以(10)*11 开头，以101 结尾;

(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 结尾，即条件(1)。使Expand(S)= 1，Ones(S)＞2 成立的唯一条件是S = (10)+1 ，即条件(3)。使Expand(S)=2，Ones(S)≥3 成立的唯一条件是S 以(10)*11 开头，以101 结尾，即条件(2)。

(⇐)(1)当S 以100 开头，以01 结尾时，设S= 100S'01 ，0S + S0 的二进制加法如下(第3 行为第1、2 相加的结果)

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

(2)当S 以(10)*11 开头，以101 结尾时，设S= 1011S'101 ，0S + S0 的二进制加法为

其中0S' +S'0 = 0S″，| S″| =| S'| +1 ，最高位无进位，或

其中0S' +S'0 = 1S″，| S″| =| S'| +1 ，最高位有进位。

无论哪种情形，Expand(S)=2，Ones(S)≥3，Lk(S)= Ones(S)- Expand(S)≥3 - 2 ＞0 ，χb(S)= 1 。

(3)当S = (10)*1 时，0S + S0 为全1 的串，Tb(S)= 1 ，χb(S)= 1 。

(a)k 为奇数。以(10)*11 开头，以101 结尾的串的个数为

(b)k 为偶数。以(10)*11 开头，以101 结尾的串的个数(首串和尾串可以共用1 个“1”)为

下面证明S 经过一步将膨胀的概率。考察满足引理2 中条件的位串个数，除以2k-2即可。分3种情况讨论:

k 为奇数时，首串和尾串可以共用1 个“1”，k为偶数时，首串和尾串可以共用2 个“1”。

S 经过一步将膨胀的概率为

尽管S 经过一步能收缩的概率不算高，实验表明，S 在m(m ＞1)步内能收缩的概率将大大增加。由于这种情况下的理论研究比较复杂。

4 结语

Collatz 问题提出以来，吸引了众多数学爱好者和数学家进行一些试探性研究。同时也诱发一些有意思的问题和方法，但较深刻的结果和突破性的结论并不多见。本文给出的串表示算法只是一种尝试，实验观察的目的是想对串满足一定分类条件下的停时现象。经验证，当串长度在300 以内时，Collatz 猜想是正确的。在图2 中，给出了长度从3到37 二进制串的最大收敛步数与长度的关系。可以观察到:最大迭代步数与长度之间几乎是线性关系。因此猜测:最大迭代步数受长度的一个线性函数控制。如果这个猜测成立，则对任意长(二进制串的长度)的数，收敛步数有限。

［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.