叙拉古猜想

HUASHI3483 · 发表于 2004-3-13 20:48:03

大家一起来做这样一个游戏：每个人可以从任何一个正整数开始，连续进行如下运算，若是奇数，就把这个数乘以3再加1；若是偶数，就把这个数除以2。这样演算下去，直到第一次得到1才算结束，首先得到1的获胜。比如，要是从1开始，就可以得到1→4→2→1；要是从17开始，则可以得到17→52→26→13→40→20→10→5→16→8→4→2→1。自然地，有人可能会问：是不是每一个正整数按这样的规则演算下去都能得到1呢？这个问题就是叙拉古猜想，也叫科拉兹猜想或角谷猜想。

　　既然是猜想，当然至今还没有得到证明，但也没有发现反例。利用计算机，人们已经验证了所有小于100*250=112589990684262400的正整数，。这是葡萄牙阿弗罗(Aveiro)大学的Tomas Oliveira e Silva的工作，用了很巧妙的编程方法。因此大家在做游戏时大可不必担心会出问题。

游戏中给出的处理过程很清楚，算法不需特殊设计，可按照游戏的叙述直接进行证。
*程序与程序注释
#include<stdio.h>
void main()
{
int n,count=0;
printf("

lease enter number:");
scanf("%d",&n);    /*输入任一整数*/
do{
      if(n%2)
      {
         n=n*3+1;          /*若为奇数，n乘3加1*/
         printf("[%d]:%d*3+1=%d\n",++count,(n-1)/3,n);
      }
      else
      {
         n/=2;       /*若为偶数n除以2*/
         printf("[%d]:  %d/2=%d\n",++count,2*n,n);
      }
}while(n!=1);          /*n不等于1则继续以上过程*/
}
*运行结果

如果要是发现一个大的正整数，经过演算结果得不到1，倒是一个了不起的发现，那就把叙拉古猜想推翻了。不过，最好还是不要急于在这个问题上花太多的时间，只有打下良好、坚实的基础，才能向这样的数学高峰攀登，也才有可能获得成功。

txy · 发表于 2004-8-1 00:03:59

<

>小弟自幼喜好这类问题，曾给出这个问题的一个论证，可是不知正错，还希望各位大虾予以批评指教！！<

> <

> 现用f1(n)表示f(n),f2(n)=f(f(n)),...fk(n)=f(f(...f(n)...)).
 则存在有限正整数m∈N,使得fm(n)=1.(以下称n/2为偶变换,3n+1为奇变换,并且称先奇变换再偶变换为全变换)克拉茨命题的证明 引理一:若n=2m,则fm(n)=1 (m∈N) 证明:当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) (k∈N),则有f(n)=3n+1=4k+1=22k+2,从而f2k+3(n)=1. 证明:证明是显然的,省略. 引理三:若n=2m(4k+1-1)/(4-1) (m∈N), 则有fm+2k+3(n)=1. 证明:省略. 定理一:集合 O={X|X=2k-1,k∈N} 对于变换f(X)是封闭的. 证明:对于任意自然数n,若n=2m,则fm(n)=1,对于n=2k,经过若干次偶变换,必然要变成奇数,所以我们以下之考虑奇数的情形,即集合O的情形.对于奇数,首先要进行奇变换,伴随而来的必然是偶变换,所以对于奇数,肯定要进行一次全变换.为了直观起见,我们将奇数列及其全变换排列如下:[em02]

txy · 发表于 2004-8-1 00:09:56

兄弟们！！图表太大了，我把他打在最后吧！！见凉！ <

> 第一行(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 (偶数).[em02]

txy · 发表于 2004-8-1 00:10:37

<

>然后我们证明经过全变换变成偶数的奇数一定大于该偶数经过若干偶变换之后得到的奇数.
设3k+1n-1=2mh (h为奇数),我们要证明 h<2*3kn-1:
h=(2*3kn-1+3kn)/2m<2*3kn-1,令a=3kn,b=2m-1,则有 2ab>a+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[em03]

txy · 发表于 2004-8-1 00:12:44

<img>

txy · 发表于 2004-8-1 00:15:29

<

>谢谢各位大虾拙见！！有兴趣和我一起研究初等数论的一些猜想问题，请参加我的话题<

> [em20]初等数论[敏感问题][em20]

txy · 发表于 2004-8-6 20:59:32

<

>图表内容！！！<

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

>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 ...÷2 1 4 7 10 13 16 19 22 25 28 31 34 ÷2 2 5 8 11 14 17 ÷2 1 4 7 ÷2 2 ÷2 1

zhaojg · 发表于 2004-8-23 19:29:20

[em07]

		自动登录	找回密码
密码			注-册-帐-号