角谷猜想的证明

角谷猜想一简介考拉兹猜想，又称为3n+1猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想，是由日本数学家角谷静夫发现，是指对於每一个正整数，如果它是奇数，则对它乘3再加1，如果它是偶数，则对它除以2，如此循环，最终都能够得到1。取一个数字如n = 6，根据上述公式，得出 63105168421。（步骤中最大的数是16，共有7个步骤）如n = 11，根据上述公式，得出 1134175226134020105168421。（步骤中最大的数是52，共有13个步骤）如n = 27，根据上述公式，得出 : 27824112462319447142712141073221614842421213641829127413741220610331015546623370035017552626379039511865931780890445133666833416750225175437711325662838504251276638319958479143871921581079323816194858242972883644182291127341367410220516154307792324616230811545771732866433130065032597648824412261184924623703510653160804020105168421。（步骤中最大的数是9232，共有111个步骤）考拉兹猜想称，任何正整数，经过上述计算步骤後，最终都会得到 1。注意：与角谷猜想相反的是蝴蝶效应，初始值极小误差，会造成巨大的不同；而3x+1恰恰相反，无论多么大的误差，都是会自行的恢复。二，逆行思考（一）角谷猜想是说，任何一个自然数，如果是偶数，就除以2，如果是奇数，就乘以3再加1。最后，经过若干次迭代得到1。也就是说，不管怎样迭代，最后都会转移到2n；不断除以2以后，最后是1。迭代过程只要出现2的幂，问题就解决了。也就是说，第一个层次是2n。（二）第二个层次是：所有奇数m乘 以3再加上1以后回到的有：m1=（2n-1）/3。也就是只要进入m1，只要一步就可以回到2n。例如：n=4时，m1=5；35+1=16。或者：1+22=5。n=6时；m1=21；213+1=64。或者：5+24=21。n=8时；m1=85；853+1=256。或者：21+26=85。n=10时；m1=341；3413+1=1024。或者：85+28=341。n=12时；m1=1365；13653+1=4096。或者341+210=1365。n=12时；m5461；54613+1=16384。即：m（x+1）=m（x）+2n；直到无穷，因为已经知道定理：n是偶数时，3|（2n-1）；m（x+1）=m（x）+2n。任何奇数进入了以后m1=2n-1）/3（有无穷多个m1=（2n-1）/3）问题就解决了，只要一步，就可以回到2n。我们可以轻而易举地找到任意大的m1。（三），第三个层次是：从一得知，有无穷多个自然数的奇数m1=（2n-1）/3任何一个奇数，只有进入5；21；85；341；.。问题就解决了。我们仅以第一个5来说，能够回到5的奇数有（52n-1）/3的有：例如：（521-1）/3=3；33+1=10；102=5。523-1）/3=13；133+1=40；408=5。525-1）/3=53;533+1=160,16032=5。527-1）/3=213;2133+1=640,640128=5。n=奇数时都有解，有无穷多个m1=（2n-1）/3.即2n|（3m1+1）。也就是说，只要进入m1=（2n-1）/3题就彻底解决了。我们可以轻而易举找到任意大的m1=（2n-1）/3。（三），从而得知，能够回到5的奇数有有无穷多个，我们仅以13来说，能够回到13的：有17；69；173；277；m（x+1）=m（x）+2n13。例如17=m2，173+1=52；524=13。17+2213=69；693+1=208；20816=13。69+2413=277；2773+1=832； 83264=13。277+2613=1109；11093+1=3328；3328256=13。1109+2813=4437.；44373+1=13312；133121024=13。.。有无穷多个m（x+1）=m（x）+2n13。它们可以回到13。只要回到问题就解决了。我们可以轻而易举找到任意大的m（x+1）=m（x）+2n13。参见下面的归纳图：（每一纵列都有无穷多个数值，横向可以无穷扩展而不重复）。例如：右上角第一个数33，333+1=100,1004=25；253+1=76,764=19；193+1=58,582=29；293+1=88,888=11；113+1=34,342=17；173+1=52,524=13；133+1=40,408=5；53+1=16,1616=1。图中每一个数都可以回到终点2n。例如：177。1773+1=532,5324=133,13325192911171352n .7093+1=2128,212816=13325192911171352n。有无穷多个数值回到任何一列，有无穷多个数值回到任何一行。显然，这样的程序可以无限制进行下去。于任何一个自然数A,（1）a.如果A为偶数，就除以2b.如果A为奇数，就乘以3加上1得数记为B（2）将B代入A重新进行（1）的运算若干步后，得数为1.这个猜想就叫做角谷猜想，在2006年这个问题被证明是recursively undecidable的了。Kurtz,Stuart A.; Simon,Janos,The Undecidability of the. Generalized Collatz Problem,Department of Computer Science. The University of Chicago,December 26,2006.折叠编辑本段错误证明最简单的证明角谷（3n+1）猜想的方法因为任何偶数都能变成2a或一个奇数乘2b。前者在不停的除以2之后必定为1，因为它们只有质因数2。而后者则只能剩下一个奇数，我们可以把偶数放在一边不谈。现在只剩下奇数了。我们假设一个奇数m，当他进行运算时，变成3m+1。如果这个猜想是错误的话，那么就有（3m+1）/2c=m，且m不等于1。我们尝试一下：当c=1时，3m+1=2m，m=-1，不符合，舍去；当c=2时，3m+1=4m，m=1，不符合，舍去；当c=3时，3m+1=8m，m=0.2，不符合，舍去；当c=4时，3m+1=16m，m=1/13，不符合，舍去；可见，能推翻角谷猜想的数只在1或以下的范围，所以没有数能推翻这个猜想，所以这个猜想是正确的。折叠编辑本段一个推广角谷猜想又叫叙古拉猜想。它的一个推广是克拉茨问题，下面简要说说这个问题：50年代开始，在国际数学界广泛流行着这样一个奇怪有趣的数学问题：任意给定一个自然数x，如果是偶数，则变换成x/2，如果是奇数，则变换成3x+1.此后，再对得数继续进行上述变换.例如x=52，可以陆续得出26,13,40,20,10,5,16,8,4,2,1.如果再做下去就得到循环：（4,2,1）.再试其他的自然数也会得出相同的结果.这个叫做叙古拉猜想.上述变换，实际上是进行下列函数的迭代 x/2 (x是偶数）C(x)=3x+1 (x是奇数）问题是，从任意一个自然数开始，经过有限次函数C迭代，能否最终得到循环（4,2,1），或者等价地说，最终得到1?据说克拉茨（L.Collatz）在1950年召开的一次国际数学家大会上谈起过，因而许多人称之为克拉茨问题.但是后来也有许多人独立地发现过同一个问题，所以，从此以后也许为了避免引起问题的归属争议，许多文献称之为3x+1问题.克拉茨问题吸引人之处在于C迭代过程中一旦出现2的幂，问题就解决了，而2的幂有无穷多个，人们认为只要迭代过程持续足够长，必定会碰到一个2的幂使问题以肯定形式得到解决.正是这种信念使得问题每到一处，便在那里掀起一股3x+1问题狂热，不论是大学还是研究机构都不同程度地卷入这一问题.许多数学家开始悬赏征解，有的500美元，有的1000英镑.日本东京大学的米田信夫已经对240大约是11000亿以下的自然数做了检验.1992年李文斯（G.T.Leavens）和弗穆兰(M.Vermeulen）已经对5.6*1013的自然数进行了验证，均未发现反例.题意如此清晰，明了，简单，连小学生都能看懂的问题，却难到了20世纪许多大数学家.著名学者盖伊(R.K.Guy）在介绍这一世界难题的时候，竟然冠以不要试图去解决这些问题为标题.经过几十年的探索与研究，人们似乎接受了大数学家厄特希（P.Erdos）的说法：数学还没有成熟到足以解决这样的问题!有人提议将3x+1问题作为下一个费尔马问题.下面是我对克拉茨问题的初步研究结果，只是发现了一点点规律，距离解决还很遥远.克拉茨命题：设 nN，并且f(n)= n/2 （如果n是偶数） 或者 3n+1 （如果n是奇数）现用f1(n）表示f(n),f2(n)=f(f(n),.fk(n)=f(f(.f(n).).则存在有限正整数mN，使得fm(n)=1.（以下称n/2为偶变换，3n+1为奇变换，并且称先奇变换再偶变换为全变换）克拉茨命题的证明引理一：若n=2m，则fm(n)=1 (mN)证明：当m=1时，f(n)=f（2）=2/2=1，命题成立，设当m=k时成立，则当m=k+1时，fk+1(n)=f(fk（2k+1）)=f（2）=2/2=1.证毕.引理二：若n=1+4+42+43+.+4k=（4k+1-1）/（4-1） (kN），则有f(n)=3n+1=4k+1=22k+2，从而f2k+3(n)=1.证明：证明是显然的，省略.引理三：若n=2m（4k+1-1）/（4-1） (mN），则有fm+2k+3(n)=1.证明：省略.定理一：集合 O=X|X=2k-1,kN 对于变换f(X）是封闭的.证明：对于任意自然数n，若n=2m，则fm(n)=1，对于n=2k，经过若干次偶变换，必然要变成奇数，所以我们以下之考虑奇数的情形，即集合O的情形.对于奇数，首先要进行奇变换，伴随而来的必然是偶变换，所以对于奇数，肯定要进行一次全变换.为了直观起见，我们将奇数列及其全变换排列如下：k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 510 2k-1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 1011 3k-1 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 71 74 77 80 83 86 89 92 95 98 101 104 107 110 113 116 119 122 125 128 131 134 137 140 143 146 149 1522 3k-2 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 763 3k-1 2 5 8 11 14 17 20 23 26 29 32 35 384 3k-2 1 4 7 10 13 16 195 3k-1 2 5 86 3k-2 1 47 3k-1 28 3k-2 1第一行（2k-1）经过全变换（3（2k-1）+1）/2=3k-1变成第二行，实际上等于第一行加上一个k，其中的奇数5,11,.6k-1又回到了第一行.以下各行是等差数列3k-2,3k-1交错排列.由于最终都变成了奇数，所以集合O对于变换f(X）是封闭的.定理二：任何奇自然数经过若干次变换都会变成1.证明：我们看到 奇数经过全变换变成为3k-1型数，3k-1型奇数经过全变换有一半仍然变成3k-1型奇数，而另一半3k-1型偶数经过除以2有一半变成为3k-2型奇数，而3k-2型奇数经过全变换又变成为3k-1型数.换句话说不可能经过全变换得到3k-2型数.下面我们只研究奇数经过全变换的性质，因为对于其他偶数经过若干次偶变换，仍然要回到奇数的行列里来.我们首先证明奇数经过若干次全变换必然会在某一步变成偶数.设2a0-1是我们要研究的奇数，它经过全变换变成3a0-1，假设它是一个奇数并且等于2a1-1,2a1-1又经过全变换变成为3a1-1=2a2-1,3a2-1=2a3-1,.3ak-1-1=2ak-1，所以a1=（3/2）a0,a2=（3/2）a1,.ak=（3/2）ak-1.所以最后ak=（3/2）ka0，要使ak是整数，可令a0=2kn,(n是奇数）.于是ak=3kn.则从2a0-1经过若干次全变换过程如下：2k+1n-1 - 3*2kn-1 - 32*2k-1n-1 - 33*2k-2n-1 -. - 3k+1n-1 （偶数）.然后我们证明经过全变换变成偶数的奇数一定大于该偶数经过若干偶变换之后得到的奇数.设3k+1n-1=2mh (h为奇数），我们要证明 h2*3kn-1:h=（2*3kn-1+3kn)/2ma+b，而这是显然的.定义：以下我们将称呼上述的连续全变换紧接着连续的偶变换的从奇数到另外一个奇数的过程为一个变换链.接着我们证明奇数经过一个变换链所得的奇数不可能是变换链中的任何中间结果，包括第一个奇数.若以B(n）表示奇数n的变换次数，m是n经过变换首次遇到的其他奇数，则有定理三：B(n)=k+1+B(m），其中k是满足3n+1=2km的非负整数.证明：n经过一次奇变换，再经过k次偶变换变成奇数m，得证.举例来说，B（15）=2+B（23）=2+2+B（35）=2+2+2+B（53）=2+2+2+5+1+B（5）=2+2+2+5+1+5=17原始克拉茨二十世纪30年代，克拉茨还在上大学的时候，受到一些著名的数学家影响，对于数论函数发生了兴趣，为此研究了有关函数的迭代问题.在1932年7月1日的笔记本中，他研究了这样一个函数：F(x)= 2x/3 （如果x被3整除 或者 （4x-1）/3 （如果x被3除余1）或者 （4x+1）/3 （如果x被3除余2）则F（1）=1,F（2）=3,F（3）=2,F（4）=5,F（5）=7,F（6）=4,F（7）=9,F（8）=11,F（9）=6,.为了便于观察上述迭代结果，我们将它们写成置换的形式：1 2 3 4 5 6 7 8 9 .1 3 2 5 7 4 9 11 6 .由此观察到：对于x=2,3的F迭代产生循环（2,3）对于x=4,5,6,7,9的F迭代产生循环（5,7,9,6,4）.接下来就是对x=8进行迭代，克拉茨在这里遇到了困难，他不能确知，这个迭代是否会形成循环，也不知道对全体自然数做迭代除了得到上述两个循环之外，是否还会产生其他循环.后人将这个问题称为原始克拉茨问题.现在人们更感兴趣的是它的逆问题：G(x)= 3x/2 （如果x是偶数）或者 （3x+1）/4 （如果x被4除余1）或者 （3x-1）/4 （如果x被4除余3）不难证明，G(x）恰是原始克拉茨函数F(x）的反函数.对于任何正整数x做G迭代，会有什么样的结果呢?经计算，已经得到下列四个循环：（1）,（2,3）,（4,6,9,7,5）,（44,66,99,74,111,83,62,93,70,105,79,59）.因为G迭代与F迭代是互逆的，由此知道，F迭代还应有循环（59,79,105,70,93,62,83,111,74,99,66,44）.G迭代还能有别的循环吗?为了找到别的循环，人们想到了下面的巧妙方法：由于G迭代使后项是前项的3/2（当前项是偶数时）或近似的3/4（当前项是奇数）.如果G迭代中出现循环，比如迭代的第t项at与第s项as重复（ts):at=as.但as/as-1,as-1/as-2,.at+1/at或等于3/2，或者近似于3/22，因而1=as/at=as/as-1*as-1/as-2*.at+1/at3m/2n这里 m=s-t,m 1）五 a=2 b=2m-1 c=1 d=1六 a=2 b=c=d=2m-1以上m为任意自然数最简单的情况：a=b=c=d=2a=2 b=1 c=1 d=1a=2 b=1 c=-1 d=0原题只是五的当m=2情况，据说中国有许多人会证明了原题，原题只是扩展的一个及其微小的部分，原题只是扩题的第五组数据成立的一个小小特殊例子。以上数据全部成立，没有一个反例，这道题非常短小，却隐含着非常丰富的数学思想的.需要用到的东西非常多，那些定理、公式都非常完美，可以表达非常普遍的数学规律。这是一个数学问题而不是什么猜想，绝对成立的，此题重在培养学生的独立思考问题的能力，以及逆向思维.其实这道题非常简单不知道是不是整体证法了对以上情况的整体证法第一步：（对于 以上的第五组数据）先构造一个2元函数 这个函数揭示了一个秘密 ：把不能被2整除的全部的自然数都转化成能被2的自然数 f(m,n) 有a （对于 以上的第五组数据）f(m,n)=2m*（2n-1）五 a=2 b=2m-1 c=1 d=1用数学归纳 整除规律 因式分解 自然数拆分.证明：（2(mn)-1）/（2n-1）=e当m和n为自然数时，e为奇数m=1 A1=（1）m=2 A2=（1,5）m=3 A3=（1,9,11）m=4 A4=（1,17,19,23）m=5 A5=（1,33,35,37,39）m=6 A6=（1,65,67,71,73,79）.的组合无限数列A（）的通项公式各小项都不能被2的m次方-1整除这个组合数列是非常简单的 只是无数个等差数列的首项.所谓的复杂 是指在不知道的情况之下的，但凡对于已经知道了答案了的人又怎么会复杂呢？顺着去验证：判断能否被a整除 若能除于a 若不能 *b+c逆着去验证：判断能否被b整除 若能除于b 若不能 *a-c折叠编辑本段编程验证折叠pascal语言Program JG;Var n, Tot: Longint;BeginReadln(n);Tot:= 1;While n 1 DoBeginWrite(n, );If Odd(n) Then n:= n * 3 + 1Else n:= n Div 2;Inc(Tot);End;Writeln(1);Writeln(STEP=, Tot);End.折叠VB语言Private Sub Command1_Click()Dim Num As LongDim