Algorithm 版 (精华区)

发信人: sino (茶水), 信区: Algorithm
标  题: 广义克拉茨(zz)
发信站: 哈工大紫丁香 (2002年08月28日21:16:05 星期三), 站内信件

【广义克拉茨】

   人们注意到克拉茨迭代所得的C数列中,取奇数的项更为重要,因此,人们引进了
简化克拉茨函数:
                                               C(x)=(3x+1)/2e(x)
 其中e(x)是3x+1所含的素因子2的个数.例如,当x=29时,3x+1=88=23*11,e(29)=3,
对应的简化C数列为
                          11,17,13,5,1,1,...
 路径由原来的18减少到5,更有利于C迭代的研究.
 一般地,设a,b是正整数,a>1,且b为奇数,广义克拉茨函数是C(x)=(ax+b)/2e(x)
 其中x取正奇数,e(x)是ax+b所含素因子2的个数.显然,a=3,b=1就是3x+1问题.
 ax+b问题就是,对于任何一个正奇数x,经过有限次的广义C迭代最终是否可得到
1?
   令人感到意外的是,ax+b问题有可能以否定的形式而解决,人们估计下面的ax+b
猜想是正确的:
   除了a=3,b=1(即3x+1问题)外,对于其他的正整数a,b(a>1,b为奇数)都可以找到
一个正奇数r,使得r的广义C迭代中始终不 出现1.
   实际上,取r=bt(t为任意正奇数),则
   C(r)*2e(r)=ar+b=(at+1)b
   如果b>1,则C(r)必能被b整除,从而r的广义C数列各项都能被大于1的数b整除,永
远的不到1,此时,猜想是正确的.
   如果b=1,则当a为偶数时,C(x)*2e(x)=ax+1恒为奇数且C数列是递增的,C迭代不
会得到1,而当a是奇数时,ax+1猜想就是:
   对于给定的奇数a>3,必定存在某个正奇数r,使得r的广义C迭代,即
C(x)=(ax+1)/2e(x)不出现1.
 1978年,克兰多尔已经证明,当a=5,181,1093时候,上述猜想是正确的.
   (1)5x+1问题:C(x)=(5x+1)/2e(x)
 取r=13,则r的广义C迭代数列是33,83,13,33,...出现循环(33,83,13),不出现1.
   (2)181x+1问题:C(x)=(181x+1)/2e(x)
 取r=27,则r的广义C迭代数列是611,27,611,27,...出现循环(611,27),不出现1.
   (3)1093x+1问题:C(x)=(1093x+1)/2e(x)
取s=(2364k-1)/1093(其中k为任意自然数),则1093+1=2364k,故e(s)=364k,
C(s)=1.可以证明这是1093x+1问题中能达到1的仅 有的一祖数,而对于其他任何正
奇数r(不等于s),则C迭代可以无限地进行下去,永远得不到1.
   此外,有人研究了7x+1问题,对于r=3的迭代项数已经超过102000,仍然看不出任
何重复的迹象,看来7x+1猜想很可能也是正 确的.但还没有从理论上加以证明.
   到目前为止,ax+1问题远未解决.


--
    我一直认为马佩军是西电编程第一高手，他编程的时候根本不是人，是指针。

                                             --《阳光男孩之大学十年》

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.224]