The 3x + 1 class record search - “3x+1问题”- 项目介绍

平常心

今天特别高兴，因为我看到有些网友已经在准备帮助我了。再次表示衷心地感谢！

     数学的创造从发现问题开始，而发现问题是离不开一定的观察与思考的。

       创造发端于问题，问题又往往发端于观察。观察不只在创造之始需要，在建立了试探性理论之后还需要继续观察。甚至在各种思维过程中也要穿插着观察。

                                                               引自张楚廷《数学与创造》（大连理工大学出版社2008年7月）

    在探索Collatz3N+1问题时采用二进制数最大的好处是有利于观察。下面例举二个Collatz树的示意图，一个是我从维基百科是下载的，这自然是一个十进制数的图；另一个是我用二进制数表示的示意图。

xx318088

@zzfwind2007

这是什么，好认真的样子……

平常心

        楼上的图一、二请网友比较。我试图寻找比较完善、清晰、有一点规律的Collatz树图，但没有找到（当然也可能是我的理解能力不够造成的，再者我的能力及接触的范围有限）。

       通常，序列是被排成一列的对象（或事件），每个元素不是在其他元素之前，就是在其他元素之后。Collatz序列的形成过程反复经历了两种不同的基本计算（乘3加1与除2），这两种计算决定了Collatz序列规律必然是两种基本规律的复合，各个元素的排列可能不局限在一条直线上。我认为，Collatz序列各元素依次分布在一个简单的三维空间（见图二），用解决线性序列的方法研究证明三维空间序列问题，自然会遇到难以逾越的障碍，这是该问题长期陷入困境的原因之一。

        只要认真观察就可以发现，图二已经反映出Collatz树的某些基本规律，但还不够明确。

平常心

xx318088 发表于 2013-4-2 21:15
@zzfwind2007

这是什么，好认真的样子……

这是一个小学生的作业。面对这么多高水平的老师，小学生没有理由不认真。

平常心

人们在长期的研究中，已经发现了或者触及到Collatz3N+1问题的许多规律，也在不断突破线性序列的束缚。

2002年，陕西师范专科学校数学研究所王念良先生提出，Collatz树是连通无回路的树状结构[1]。从树的角度去研究这个问题，比单纯从线性序列的角度是一个进步。可惜该文对Collatz树的具体结构及各深度上顶点的数值关系并没有深入具体的探讨。

周云才、周宝兰先生发表在长江大学学报（理工卷）2007年4卷1期上的文章：《Collatz猜想探讨》使用了一个有趣的比喻：“一个Collatz波就像是一个毛毛虫，每一次的变换就是此毛毛虫的一次蠕动。先是弓背(能量的聚积)，然后伸展(能量衍射)，同时在其尾端(波的开始端)排泄能量，而在其头端(波的末端)吸收能量。每一条毛毛虫都经历了一个出生一成长一萎缩一死亡的过程。”这与二进制数的迭代序列中，数字长、短的反复变化，最后归结到1的情况非常相似。

2008年，内蒙古科技大学郝生旺先生在“中国科技论文网”上发表了《3n+1问题的直接证明》。文章认为，“3n+1问题是一类迭代数列整体性质的证明问题。”并“利用共尾数列及良序原理”，给出了一个证明。“共尾数列”实质上是树状结构反映。郝先生虽然对迭代数列的一些具体规律作了较深入的研究，某些地方已经揭示出该猜想的基本特点，但仍然有一些局限，对所有数列的集合——“树”的“整体”研究不足。

2011年，(德)Gerhard Opferd的《An analytic approach to theCollatz 3n+1 problem》(预印本)介绍，“Berg and Meinardus, 1994,1995，introduced a pair of linear functional equations” ，“The simultancous solutions of the two functional equations contain a simple two dimensional space,denoted by △2,and if one could show that △2 is the only solution,the Collatz conjecture would be true.（2个函数方程的联立解构成一个简单的二维空间△2，如果有人能证明△2是唯一的解，那么 Collatz 猜想就是成立的。）”Gerhard Opferd在此基础上继续深入研究，他一度认为已经证明了该猜想。当时，一条Collatz曾经的学生证明了该猜想的消息不胫而走。仅过了一个月，Gerhard Opferd就断然宣布自己的证明有一个漏洞，证明仍需继续。

将Collatz序列放进一个二维空间进行分析研究，无疑是一大进步。在利用现代数学手段的同时，人们似乎比较容易忽视，我们熟悉的十进制数无形中妨碍了我们对Collatz序列基本规律的观察、分析。

---

[1] 王念良，2002，《Collatz问题的证明》，商洛师范专科学校学报第16卷第2期.

平常心

《Collatz树的基本规律》主要观点

若对于所有奇数猜想成立，则对于所有的自然数猜想亦成立。

将奇数划分为两类：≡101(mod1000）或≢101(mod1000）。

定理1：若  m≡101(mod1000）

必有 m = m0×10^2(k+1)+ (10^2(k+1)-1)/11且(and)D(m)=D(m0)

（m∈M k∈N m0≢101(mod1000））

定义3：若 m1≢101(mod1000）>11,必有  m1= n×10j+1 +10j -1

当  n＝0(mod2)且j＝0(mod2)  或 n＝1(mod2)且j＝1(mod2)时

令  m2=(m1-1)/10= n×10^j+10^(j-1) -1

当(If)  n＝0(mod2)且j＝1(mod2) 或 n＝1(mod2)且j＝0(mod2)时

令(Put)  m2= m1×10+1= n×10^(j+2) +10^(j+1) -1

我们称m1、m2为孪生数对(m1、m2∈M n∈N j>=1 )。

定理2：若 m1、m2为孪生数对，则  D(m1)=D(m2)。

若所有孪生数对中较小的奇数符合猜想，则所有自然数符合该猜想。

Collatz序列的二进制数变化可以看作，尾部字符减少、前端字符增加的综合结果。

定义４：Collatz树上任何一顶点m的所有双亲中，一对最小双亲——mx1、mx2，称作该项的最小双亲对。

当m≡ 0（mod11）时，

      mx1 = m/11×10^3+1         mx2 = m/11×10^4+1

当m≡ 1（mod11）

      mx1 = (m－1)/11×10^2+1     mx2= (m－1)/11×10^5+10001

当m≡ 10（mod11）

      mx1 =(m－10)/11×10+1     mx2 =(m－10)/11×10^6+110001

m与其最小双亲对相比，尾部位数减少的平均值恒等于3.5：

A = (B(mx1)+B(mx2))/2－B(INT(m/3)) =3.5    (m∈M)

（B(m)=ln(m)/ln(2)+1，该函数之值为m的二进制数位。）

（INT（A）为向下取整函数）

当深度差为n时，二进制数前部字符增加的个数由下式确定：

B = INT(ln(m0×3n)/ln(2))－INT(ln(m0)/ln(2))

当n足够大时，上式可简化为：B ≈ INT(n×ln(3)/ln(2))。

平常心

      上面介绍了我的主要观点，下面将逐一介绍。再次声明，我是一个也遇到低水平的数学爱好者，在各位面前是一名诚恳听取批评意见的小学生，望各位不吝赐教。实现介绍一个附带的问题，我采用二进制数计算（上下标在、序号等仍用十进制数），其基本方法如下文（只是一个简单而笨拙的方法，因为我采用手工计算）：
           二进制数的有关计算问题

㈠判断二进制数是否可被11（3）整除的方法

由于，2^2k≡1(mod3)

故： (2^2(k+i)+2^2k+1)×2j≡0(mod3)  (k∈N, i、j∈N)

例如(2^4+2^2+1))×4=84;(2^8+2^4+ 1)×8=2184;( 2^10+2^2+ 1)×2=2058……

当i=0时，(2^2(k+i)+2^2k+1)×2j=(2^(2k+1) +1)×2j≡1(mod3)

例如: (2^3+1)×32=288;  (2^5+ 1) ×4=132;  (2^7+1) ×2=258……

将以上二式化作二进制数就是：

(10^(2k+1)+1)×10j≡0(mod11)

(10^2(k+i)+10^2k+1)×10j≡0(mod11)

故，凡全部由以下三类字符段嵌套组合而成的数字，定为11(3)的倍数：

①11、1111、111111……（3、15、63……）

②1001、100001、10000001……（17、33、129……）

③10101，1010001，101000001……100010001……（21、81、321……273）

反之必定不是11的倍数。

    例如：1111001011100101可以分解为：1111、1001、10000001、1001等，因而它是11的倍数。

在此基础上，可进一步推演出更实用的复杂组合:

令:A=00……0（由奇数个0组合的字符串）

   B=1……1（中间为任意多个字符组合，但不包含A字符串）

任何二进制数均可由0、1与A、B字符串组合而成，其中：

0≡0（mod11） 11≡0（mod11） 1A01≡0（mod11） 1ABA1≡0（mod11）

1≡1（mod11） 1A0≡1（mod11） 1ABA≡1（mod11）

1A≡10（mod11） 1A1≡10（mod11） 1AB≡10（mod11） 1 ABA0≡10（mod11）

由左至右逐个划去≡0（mod11）的字符串，最后剩余的字符串即可确定被11（3）整除后的余数。

例如：10111111001110000111111000011111≡10（mod11）

      100111100011001001111000000001111111101≡0（mod11）

      1000011000110011111000000111111011000≡1（mod11）

㈡Collatz问题中的二进制数计算

一个二进制数乘11（3），相等于这个二进制数的错位加法。

101×11=1111              101×11+1=10000

10101×11=111111         10101×11+1=1000000

1010101×11=11111111    1010101×11+1=100000000

……

11×11=1001              11×11+1=1010

111×11=10101            111×11+1=10110

1111×11=101101          1111×11+1=1011110

……

以上是基本计算格式。利用这些计算格式能够较快地对二进制数从左至右进行乘11（3）加1计算。

平常心

       这一部分算是开场白吧，基本上是照搬别人的，没有什么新的东西。我认为重要的是对为什么要将研究范围缩小到奇数，这不单单是一个范围问题。其实质是将一个三维空间的序列简化为二维平面序列的第一步。许多专家学者之所以坚持不缩小研究范围，可能与对这个问题的认识有关。许多时候认识比证明本身重要得多。

Collatz树的基本规律

   业余数学爱好者  郑敏

对于所有正整数n我们定义一个序列Ci(n)，其中：
          C0(n) = n
并且对于所有i>0有：
        若   n＝0(mod2)   Ci(n) = 3Ci-1(n)+1
        若   n＝1(mod2)   Ci(n) = Ci-1(n)/2                     (1.1)
若经过有限的迭代次数k，必有Ck(m) =1。这就是Collatz问题（猜想）。
本文采用二进制数运算(序号、幂指数、上下标仍采用十进制数)。若对于所有奇数猜想成立，则对于所有的自然数猜想亦成立，故上式可简化为：
       Ci(m) = (11Ci-1(m) +1)/ 10e(m)   （m∈M）          (1.2)
      （式中e(m)表示使偶数11m+1能被10e(m)整除的最大自然数）[1]
       定义1：对于所有的奇数m令k为满足 Ck(m) =1 的最小上标，我们称k为m的归一步数(Delay), 并记作
D(m)[2]。若Ci(m1)= Ci(m2)(m1≠m2  m1、m2∈M  i∈N)，则D(m1)=D(m2)，并且称m1、m2为兄弟项。
       定义2：在Collatz序列(中，Ci(m)的前一项 Ci-1(m)为该项的双亲；其下一项 Ci+1(m)为该项的孩子。

---

[1]见邬家邦,2001. 3N+1猜想. 长沙：湖南大学出版社.100.

[2] 归一步数(Dela)借用了荷兰学者Eric Roosendaal《On the 3x + 1 problem》网站上的概念。由于研究范围不同（Eric Roosendaal是根据（1.1）式推算D(m)的数值，而我根据（1.3）式推算），得出的具体数据有较大区别，但基本规律是一致的。不影响对问题的研究探讨。

平常心

       对于Collatz3N+1猜想的证明来说，下面介绍的是非常简单而又最重要的定理。
       定理1，虽然是我独立发现的，但我很快就了解到，早就有人发现了它。只可惜人们看到了这个规律，却没有真正认识它的重要性，否则，该猜想在若干年之前早被证明了。采用二进制数之后，这个定理从直观的角度就可以证明，但数学是严谨的，我还是要写一点证明。利用这个定理，我们可以将Collatz序列化为一个有规律的二维空间序列。

                          基本定理（1）

定理1：若  m≡101(mod1000）

必有 m = m0×102(k+1)+ (102(k+1)-1)/11 且(and)D(m)=D(m0)

（m∈M k∈N m0≢101(mod1000））

证明 ：m≡101(mod1000）

设m = mk×102+1

若  mk≡101（mod1000）

m =( mk-1×102+1)×102+1= mj-1×104+102+1

……

直至 m0≢101（mod1000）

m =m0×102(k+1)+102k+102(k-1)+……+102 +1

= m0×102(k+1)+（102(k+1)-1）/11

C1(m)=(11×m+1)/ e(m)=( (11×m0+1)×102(k+1))/ e(m)

           =( (11×m0+1)×102(k+1))/(e(m0) ×102(k+1))

           =(11×m0+1) / e(m0)= C1(m0)

    故  D(m)=D(m0)

例如  C1 (111)=(11×111+1)/ e(111)=10110/10=1011

C1(111010101)=(11×111010101+1)/ e(111010101)

=10110000000/(107)=1011

故有  C1(111010101) = C1(111)=1011  (C1(469) = C1(7)=11)

平常心

                     基本定理（2）
定义3：若 m1≢101(mod1000）>11,必有  m1= n×10j+1 +10j -1
            当  n＝0(mod2)且j＝0(mod2)  或 n＝1(mod2)且j＝1(mod2)时
            令  m2=(m1-1)/10= n×10j +10j-1 -1
            当  n＝0(mod2)且j＝1(mod2)  或 n＝1(mod2)且j＝0(mod2)时
            令  m2= m1×10+1= n×10j+2 +10j+1 -1我们称m1、m2为孪生数对(m1、m2∈M n∈N j>=1 )。
定理2：若 m1、m2为孪生数对，则  D(m1)=D(m2)。
    证明：C1(m1) = (m1×11+1) / 10e(m1)  (n×11+1) ×10j +10j-11
                    c2(m1) = (n×112+11+1) ×10j-1 +10j-2 -1
                     ……

当  n＝0(mod2)且j＝0(mod2)(or) n＝1(mod2)且j＝1(mod2)时

Cj-2(m1) = (n×11j-2+(11j-3+11j-4+……+11+1)) ×103 +102 -1
Cj-1(m1) = (n×11j-1+(11j-2+11j-3+……+11+1)) ×102 +10 -1 = (n×11j-1+(11j-1-1)/10) 102 +1
Cj-1(m2) =n×11j-1+(11j-1-1)/10

当  n＝0(mod2)且j＝1(mod2) 或 n＝1(mod2)且j＝0(mod2)时

Cj-1(m1) = (n×11j-1+(11j-2+11j-3+……+11+1)) ×102 +10 -1
Cj(m1) = (n×11j+(11j-1+11j-2+……+11+1)) = n×11j+(11j-1)/10

Cj-1(m2) =(n×11j+(11j-1)/10) 102 +1

根据定理1可得  D(m2)=D(m1）

平常心

刚才看了一段第15届青歌大赛节目。一位评委说，过错是暂时的，但错过是终生的遗憾。
我原本是想通过中国分布式计算与(荷)Eric Roosendaal联系，一是表示感谢，而是请教有关问题。没有想到这里就有一个很好的论坛，而且有高人表示要帮助我。过错是暂时的，但错过是终生的遗憾，我必须努力，不要错过这个学习的机会。

平常心

       我在这里采用了一个特殊的符号——[ …… ]。主观上是想用一个比较简洁的符号表达一个固定的数学演变过程，但由于个人数学修养差，找不到合适的符号。如果有更好、更合适的表达方法，希望各位专家、网友帮助。

                                                           Collatz树
      根据以上定理可将奇数划分为两类：≡101(mod1000）或≢101(mod1000）。
      若所有孪生数对中较小的奇数符合猜想，则所有自然数符合该猜想。1与11符合猜想，主要结构特征与孪生数对类似，亦视为孪生数对。

       据此对（1.2）式修改如下：

             (m)= [(11[Ci－1(m)] + 1)/10e(m)]      (m∈M)               (1.3)

       中 [……]的含义是：

            A = m0×102(k+1)+(102(k+1)-1)/11   (A、m0∈M k∈N)

           [A] = m0

       若 m= n×10j+1+10j -1  (m∈M n≧0  j≧1 )

           当 n＝0(mod2)且j＝0(mod2)  或 n＝1(mod2)且j＝1(mod2)时

             【m]= (m-1)/10

       否则  [A] = A

       将上式生成的Collatz序列汇聚在一起，形成Collatz树。其中每个顶点有无限多个双亲，根据双亲的结构，可分为两列。

       定义４：Collatz树上任何一顶点m的所有双亲中，一对最小双亲——mx1、mx2，称作该项的最小双亲对。
        Collatz树的根——1，没有孩子，它的最小双亲对是10001和1110001，它们将Collatz树分为上下半区。根据（1.3）式推导出确定最小双亲对的公式：
        当m≡ 0（mod11）时，

          mx1 = m/11×103+1           mx2 = m/11×104+1                                  (1.4-1)

       当m≡ 1（mod11）

          mx1 = (m－1)/11×102+1    mx2 = (m－1)/11×105+10001                     (1.4-2)

       当m≡ 10（mod11）

          mx1 =(m－10)/11×10+1    mx2 =(m－10)/11×106+110001                   (1.4-3)

        在最小双亲对基础上将其余双亲按大小分级如下：
       一级双亲 = mx1×106+110001 或 mx2×106+110001
       二级双亲 = (mx1×106+110001)×106+110001    或   (mx2×106+110001)×106+110001
       三级双亲 = ((mx1×106+110001)×106+110001)×106+110001    或  ((mx2×106+110001)×106+110001)×1106+110001
       …………
       i级双亲 = mx1×106i+110001×(106i－1)/(106－1)    或   mx2×106i+110001×(106i－1)/(106－1)

       根据双亲对的级别，我们就又可以将Collatz树划分级别如下：
       基干图(Main force digraph)：全部由最小双亲对组成的Collatz树(图一)。
       一级扩大图：全部由基本顶点和一级双亲组成的Collatz树（图二）。
       二级扩大图：全部由基本顶点和一、二级双亲组成的Collatz树。
       ……
       i级扩大图：全部由基本顶点和一至i级双亲组成的Collatz树。
       显然，基干图是一个深度无限大、没有叶子的满二叉树。各级别扩大图中，每个顶点的双亲也是固定有限的，可以看做若干满二叉树的组合。

平常心

楼上的图一

平常心

57#图二

平常心

Collatz树的基本规律

Collatz序列各项数字的大小变化变幻莫测，令人困惑。采用二进制数后发现，这种变化是尾部字符不断减少、前端字符不断增加而综合形成的，前后变化各有固定的规律(图三)。

                              

观察(1.4-1)、 (1.4-2)、 (1.4-3)式可以发现mx1、mx2的前端字符相同，但后部字符个数和恒为7，也就是说，将m与其最小双亲对相比，尾部位数减少的平均值恒等于3.5(以下计算采用十进制数)：

A = (B(mx1)+B(mx2))/2－B(INT(m/3)) =3.5    (m∈M)

（B(m)=ln(m)/ln(2)+1，该函数之值为m的二进制数位。）

（INT（A）为向下取整函数）

根据上式，可以推算出，在同一级别的Collatz图中，各深度下所有顶点二进制数尾部字符数逐级减少的平均值A为：

基   干    图       3.5

一级扩大图       3.5+12/4=6.5

二级扩大图       3.5+12×（1+2）/6=9.5

三级扩大图       3.5+12×（1+2+3）/8=12.5

……

i级扩大图      3.5+12×（1+2+3……+i）/2×（i+1） = 3.5+3i

设M0为某深度下一顶点的值，经过n次迭代计算后得mn，二进制数前部字符增加的个数由下式确定：

B = INT(ln(M0×3n)/ln(2))－INT(ln(M0)/ln(2))

当n足够大时，上式可简化为：B ≈ INT(n×ln(3)/ln(2))。

显然，当当深度差很小时，B值与顶点m的数值关系较明显，为1或2；随着深度差n的加大，其影响越来越小；当n足够大时，可或略不计。

综合以上变化规律推导出以下结论：在同一级别的Collatz图中，若两层深度差为n，则所有顶点二进制数平均数位之差Bn由下式确定（注意：上下半区应分别统计）：

Bn = INT（（A－INT(ln(M0×3n)/ln(2))+INT(ln(M0)/ln(2)) )×n）

或：Bn =INT（（A－㏑(3)/㏑(2)）×n）  （n∈N）         (1.5)

由于A>㏑(3)/㏑(2)，因而可以确定在Collatz树上，不同深度（归一步数）下的所有顶点的二进制数位数的平均值随着深度的减小而递减。这就决定了，最小的奇数1是Collatz树的根，也就是说Collatz猜想是成立的。