规律的Collatz树——用二进制数解读3N+1猜想

塞上平常心

[这个贴子最后由塞上平常心在 2010/12/03 09:06pm 第 1 次编辑]

(整理之后重新发表,欢迎批评指正)
                                规律的Collatz树
                                   ——用二进制数解读3N+1猜想
                                银川数学爱好者  郑敏
    [提要]本文利用二进制数的特点首次提出“谷值数”概念，并在此基础上将3N+1猜想的Collatz树简化，简化后的Collatz树是谷值数的集合，故可以称为谷值树。谷值树比较“完整”，也比较“规范”，它去除了容易将人引入迷途的“枝叶”，为人们探索该猜想的规律创造了条件。……
    （一）令人茫然的数学难题
    从任一正整数n出发，进行如下的一系列运算：若n是奇数，就求3n+1；当n是偶数，就除以2……，如此反复计算，最终必然在有限步运算内达到1。这就是 问题 (或称 猜想)。
3N+1猜想的数论函数定义如下：
         (n∈N)             （1.1）
    依上式进行迭代得到一个迭代轨迹序列：T(n),即：
        T(n) = (C0(n), C1(n), C2(n), C3(n),……)
    其中：C0(n) = n
    经过有限的迭代次数k，必可使得Ck(n) =1。
   
    依上式进行的迭代曾经是多数学者所采用的迭代，称为通常迭代。
    显然，若所有奇数符合3N+1猜想，则所有的自然数也符合3N+1猜想，因此许多人采用压缩迭代代替通常迭代，其函数定义如下：
          C(m) = (3m + 1)/ 2e(m)                      (1.2)
    （式中 e(m)表示使偶数3n+1能被2e(m)整除的最大自然数）
    采用压缩迭代后自然数n的轨迹序列，比通常迭代下的序列要短得多。但是，问题的简化，并非问题的证明，当我们展开该问题的Collats树时，看到的依然是一片“杂乱无章、无规律可循”的数字。
    正是这杂乱的表象，让人们无从下手，甚至试图寻找不符合猜想的反例。然而成百万、千万的数据计算不能否定该猜想，时光流逝，几十年转瞬而去，这个连小学生都能明白的课题，其证明之难却依然令人茫然不知所措。
    当我看到这个猜想的时候，一个念头挥之不去：采用二进制数将是解决该猜想的有效途径。
    采用二进制数代替我们习惯的十进制数后，上式变为：
          C(m) = (11m + 1)/10e(m)

塞上平常心

                    （二）计算简单方便的二进制数
    二进制数简单：它只需0、1两个字符。
    正因如此，二进制数比我们习惯的十进制数要长得多。虽说现在人们对二进制数已比较熟悉了，但它的运算主要是在计算机内部在进行，人们在日常生活、工作中基本上仍然采用十进制数。我曾经请求他人帮助我编写一段二进制数的计算程序，对方显得很不理解：二进制数，多不方便呀，那么长！
    问题在于， 3N+1猜想的每一次迭代运算均为乘3、除2（或2的倍数）的简单的有规律的运算。
    除2（或2的倍数）只不过是去掉数字尾部所有连续的0字符。对于（1.2）或（1.3）式中的 e(m)值，在十进制中，一般需要计算，而在二进制数中，可以直观判断出。（如无说明，以下所有的运算均采用二进制数字，但序数、上下标、说明注释仍然采用十进制数。）
⑴如果奇数m最右端的1字符段有k个1（k>=2）,11m+1的末尾必定只有一个“0”:
        

塞上平常心

                      （三）结构简单直观的二进制数
    设有奇数m，则由（2.4）可导出下式：
        C(m×10^2k+01……01) = C(m)                            （3.1）
                    k个01
    式中k为任意自然数
    例：C(1101) = C(11) ，C(10110101) = C(1011)……
    上式告诉我们，m×102k+01……01和m的迭代计算结果是相同的，因此在我们的研究中，一般可以用m替代m×102k+01……01。
    这似乎是一个很寻常的公式。人们在十进制数条件下，早就发现了该规律。但是，在二进制数中，你一眼就可以发现m×102k+101……01 与m之间的联系。若换成十进制数，很多情况下，通过计算你才能确定。
    不要小看这一点，它也许在向人们预示3N猜想的正确性。
    在任意一个二进制自然数的3N+1迭代计算过程中，尾部的连续的1字符串迟早会化为单独的1字符，而其中间哪些1字符串无论有多么长，每二次迭代计算，都会将它减少3个字符。与此同时，该自然数中间连续的0字符串也在作相应的变动。这个变动的总趋势是：使0、1字符均匀分布。最均匀的自然就是0与1间隔分布，不用说，这样的数字与1是等同的。当然，一般情况下，仅仅是数字的某一部分趋于均匀分布，当数字的尾部出现这种现象时，迭代序列的下一项就有了明显减小。如此一步步演变，最终到达序列的终点“1”。
    例：     100001111111111001111110000111
            110010111111110110111101001011
          1001100011111110010011011110001
         111001010111110101110100110101
       101011000001111000010111101
     10000001000101101001000111
    11000001101000011101101011
    这不是证明，但你在用二进制数的运算中时刻都能感受到数字变化的趋势。
（3.1）式虽简单，但它是该猜想的基础，有可能是我们证明此猜想正确性的起点。

申一言

   万法归一！
   万数归零！

塞上平常心

                           （四）美是有范围的
    一个问题的解决关键在于掌握问题的规律.
    3N+1猜想尽管比较复杂，人们在不断的研究中还是发现了不少规律性的东西。我们认真研究这些规律后发现，这些规律性的东西，在二进制数下往往是十分明显、直观的。人们花费大量精力发现表述它们，一个重要的原因是十进制数的结构掩盖或扭曲了自然数本身的规律。于是人们不得不借助一些新的概念、定义来描述它们。
    奇偶矢量*是其中一个典型的例子。
    邬家邦先生在《3N+1猜想》一书中介绍说，“在自然数与奇偶矢量集之间存在一个很漂亮的一一映射”，并用大量篇幅，介绍了前人利用奇偶矢量的概念得出的成果，以淋漓尽致地展现奇偶矢量的数学之美。
    邬家邦先生还认为，“在压缩迭代下奇偶矢量的作用则完全丧失。”其实当我们应用二进制数研究该猜想时，压缩迭代的次方序列**就以另一种形式展现出“奇偶”矢量的实质内容。若将次方序列各项直接用0的个数展示出来，并将各项的第一个0改为1，然后依次排列，其结果与奇偶矢量完全一致。
    例如：131的奇偶矢量为：ν={11000100011101001000}
    将131换算成二进制数：10000011，这样我们可以很方便地得出其次方序列：
        E(10000011)={e(10000011),e(11000101),e(100101),e(111),e(1011),e(10001),e(1101),e(101)}={1,100,100,1,1,10,11,100}
    由此可得出10000011（131）的奇偶矢量为：
        ν={1,1000,1000,1,1,10,100,1000}
    (注意:此式中的1和0是奇偶符号,在上式中则是代表0 的个数的二进制数)
   
    《3N+1猜想》中专门有一节介绍由奇偶矢量νk（n）求自然数n的算法。用νk(n)求二进制数n，算法更简单，且不需设中间变量，按照二进制数的计算规律直接在纸面上写即可（具体算法略）。美的的东西也只适用于一定的范围，由于二进制数的结构已经比较明显地展现了奇偶矢量的主要特性，我认为，采用二进制数时可以抛弃这一概念。
    下面是《3N+1猜想》23页定理3.1的内容：

    这个定理实质上是这样一些二进制数数对：
        ……00101      ……101101    ……0011101    ……
        ……00110      ……101110    ……0011110    ……
    只要掌握了式（3.1）和（4.1）、（4.2）就很容易理解该定理，无须再单独列出。
    此外，《3N+1猜想》一书中的定理3.3⑴、3.3（2）、3.4、3.5（可能是作者一时疏忽，书中出现了两个定理3.3， 我们暂且称先出现的为定理3.3（1），后出现的是定理3.3（2））也都可以用二进制数直接展示出来，我在科学网的文章中已做了介绍，这里就不再介绍了。
    *：“奇偶矢量”——邬家邦：《3n+1猜想》11页：
    设自然数n的轨迹序列为
        T(n) = {C0(n),C1(n),C2(n),…Ci(n),…}={n0,n1,n2,…ni,…}
    对i=0，1，2，…令
        Xi(n) = 0, 当 n=0(mod2)时;
                1, 当 n=1(mod2)时;
    得矢量  ν(n) ={x0(n), x1(n), x2(n),…xi(n),…},
    称为n的奇偶矢量;而矢量
    νi(n) ={x0, x1, x2,…xi-1,…}
    称为n的长为i的奇偶矢量……
    **：“次方序列”——邬家邦：《3n+1猜想》108页定义8.5：“设n∈Nd,记T(n) = {C0(n), C1(n), C2(n), C3(n),……}，则E(n)={e(n0),e(n1),e(n2),……}称为n的次方序列。”

塞上平常心

    （五）奇数分类及研究重点
    任意一个二进制奇数m，均由若干1字符串和0字符串组成，其前后（或左右）两端必定是1字符串。根据奇数的结构，我们将它们划分为三类：
    A 类：尾部为k（k≥2）个连续的1字符串；
    B 类：尾部单个1字符串，这个之前是k（k≥2）个连续的0字符串；
    C类：A、B类之外的奇数均属于C类，它们的尾部结构为单个的0与单个的1字符间隔出现的形式，即“1010……101”。
    任意的奇数迭代序列中，这三类数字总是分段间隔出现的。
    A类数字段的首项≡1（mod11）或0（mod11），其余各项≡10（mod11）。段内各项数字的尾部的1字符逐项减少一个，但数值逐项增加。
    B类数字段首项≡10（mod11）或0（mod11），其余各项≡于1（mod11）。各项尾数的0字符逐项减少二个”，数值逐项减小。
    C类数字子在迭代序列中总是单个出现，它的子项（即后一项）数值必然是减小的。
    因此，在一个迭代序列之中，B类数字段首项总是局部的峰值，而A类数字段的首项总是局部的谷值（最小值）。
    根据（3.1）式，必定与某个A（或B）类奇数等同。
    另外，假如有若干自然数是该猜想的反例，它们的迭代序列也必定包含这三类数字，他们之中那个最小的奇数，自然也是某个A类数字段的首项。
    鉴于以上两点，我们将研究的重点放在A类数字段的首项上。
    尾部结构为“0011”的 A类数字等同于相应的尾部结构为”001”的B类数字，故在我们的研究中，将它们排除在重点研究的A类数字以外。
    除了那些明显符合该猜想的奇数外，任何一个奇数的迭代序列中必定包含若干“A类数字段首项”，所以我们的研究大大缩小了研究范围，且是有代表性的。
    下面你将会看到，这样也使这个令人茫然的数学难题的许多规律逐步展现在我们面前。

塞上平常心

                  （六）谷值数及谷值数的根——G
    A类数字段的首项总是成双成对出现的。例如：11111、111111；1011、10111；110011000111、1100110001111……等等。前面介绍过的（4.1）、（4.2）式已经包含了这类数对，在迭代运算中，它们相互之间是等同的，我们称其中较小者为“谷值数”。
    按照谷值数的结构，我们将其划分为三部分：其一是尾部连续的1字符串；其二是这个字符串前的一个0字符；除去前两部分，最后就是该谷值数前面剩余的字符了，我们称之为谷值数的根——G。
    例如：       0011111
                 1011
                100111111111
          110011000111
    以上数字中有下划线的部分即为该谷值数的根。
    假如某谷值数m 的根G ≡ 1（mod11），那么，其子项C（m）必定小于m，也就是说,这个m绝非谷值数。故有：
         G ≡ 0（mod11）或10
    从另一个角度来说，凡是G ≡ 0（mod11）或10的自然数，即可组成一系列的谷值数。显然在二进制数中，位数相同的G的数量以及谷值数的数量都是确定的。
    以下将谷值数的根G分两行依次列出，左边的G构成的谷值数是奇数位，右边则仅构成偶    数位的谷值数。
G       (奇)             (偶)
          0                 
         11               10
        110              101
       1001             1000
       1011             1100
       1111             1110
      10010            10001
      10100            10101
      11000            10111
      11010            11011
      11110            11101
     100001           100000
     100011           100100
     100111           100110
     101001           101010
     101101           101100
     101111           110000
     110011           110010
     110101           110110
     111001           111000
     111011           111100
     111111           111110
    1000010          1000001
    1000100          1000101
    1001000          1000111
    1001010          1001011
    1001110          1001101
    1010000          1010001
    1010100          1010011
    1010110          1010111
    1011010          1011001
    1011100          1011101
    1100000          1011111
    1100010          1100011
    1100110          1100101
    1101000          1101001
    1101100          1101011
    1101110          1101111
    1110010          1110001
    1110100          1110101
    1111000          1110111
    1111010          1111011
    1111110          1111101
   …………         …………
    以下是不同位数谷值数的总项数表(该表及其S的计算均采用十进制数):
    位数n：    3  4  5  6  7   8   9  10   11   12   13……
    项数S：    1  0  2  2  6  10  22  42   86  170  342……
      ∑S：    1  1  3  5  11  21  43  85  171  341  683……
    当n为偶数时，令：n = 2k
        Sn  =  2^2(k-2) - 4(4^(k-3)-1)/3 – 2
       ∑Sn = 4^( k -1)/3
    当n 为奇数时，令：n = 2k-1
        Sn  =  2^(2(k-2)-1) - 2(4^(k-3)-1)/3
       ∑Sn = 4^2( k -2)/3

塞上平常心

                  （七）简化Collatz树——谷值树
   
    了解3N+1猜想需要研究自然数的迭代序列，但更应从整体上研究这些序列之间的联系和变化。Collatz树是自然数迭代序列的集合，理应成为我们研究该猜想的重要对象。可惜这颗树实在是太大太大，我们置身其中，一脸茫然，不知所措。一般研究者给出的Collatz树的图，不过是给出一个“树”的概念（参看图0701）。
        
                           图0703  简化Collatz树
    简化的Collatz树是谷值数的集合，故可以称为谷值树。它虽然是简化的树，但也可以说是比较“完整”的，也比较“规范”。图中显示了2^15以内的部分数据，且包含了2^11以内的所有符合要求数据，位数相同的数据均安排在一列之中。

塞上平常心

                            （八）谷值数的迭代计算
    若某谷值数m的尾部为k个连续的1字符，根据（2.1）式可推导出：
     C0(m) = Gk×10k+1+ (10k-1+10k-2+……+10+1) = Gk×10k+1+(10k-1)
     C1 (m) =( Gk×111 +1) ×10k+ (10k-2+……+10+1)
     C2 (m) =( Gk×112 +（11+1)）×10k-1+ (10k-3+……+10+1)
         ……
     Cj (m) =（Gk×11j + (11j-1+11j-2+……+11+1)）×10k-j+1+(10 k-j+1+……+10+1)
           =（Gk×11j + (11j-1)/10）×10k-j+1+(10 k-j+2-1)
     ……
     Ck-1 (m) =（Gk×11k-1 + (11k-2+11k-3+……+11+1)）×102+ 1
     Gk = Ck (m) = Gk×11k + (11k-1+11k-2+……+11+1) = Gk×11k +(11k-1)/10
                                                                   (8.1)
    谷值数的计算是非常简便而有规律的。根据上式我们可以进行某个固定的谷值数的根G有关的谷值数的迭代运算，并将计算结果列表。一般的迭代运算即可从这些表中查出结果。以下是G = 0、G = 10时的部分运算结果：

    (注：由于以上数字太长，仅留其尾部的48位字符)
    ……
    谷值数运算的规律预示着，该猜想不会存在反例。我们应当此基础上探索严密的证明。