Algorithm 版 (精华区)

发信人: sino (茶水), 信区: Algorithm
标  题: 原始克拉茨(ZZ)
发信站: 哈工大紫丁香 (2002年08月28日21:12:46 星期三), 站内信件

【原始克拉茨】

   二十世纪30年代,克拉茨还在上大学的时候,受到一些著名的数学家影响,对于数
论函数发生了兴趣,为此研究了有关函数 的迭代问题.
在1932年7月1日的笔记本中,他研究了这样一个函数:

{
2x/3     x被3整除

F(x)=
(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进行迭代,克拉茨在这里遇到了困难,他不能确知,这个迭代是否会
形成循环,也不知道对全体自然数做迭代除 了得到上述两个循环之外,是否还会产
生其他循环.后人将这个问题称为原始克拉茨问题.现在人们更感兴趣的是它的逆问
题:


{
3x/2     x是偶数

G(x)=
(3x-1)/4 x被4除余3


(3x+1)/4 x被4除余1

不难证明,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重复(t<s):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/at≈3m/2n
   这里 m=s-t,m < n
   即 2n≈3m
   log22n≈log23m
   故 n/m≈log23
   这就是说,为了寻找出有重复的项(即有循环),应求出log23的渐进分数n/m,且m
可能是一个循环所包含的数的个数,即循环 的长度.
   log23展开成连分数后,可得到下列紧缺度不同的渐进分数:
   log23≈2/1,3/2,8/5,19/12,65/41,84/53,485/306,1054/665,24727/15601,..
.
   渐进分数2/1表明,31≈22,循环长度应为1.实际上恰存在长度为1的循环(1).
   渐进分数3/2表明,32≈23,循环长度应为2.实际上恰存在长度为2的循环(2,3).

   渐进分数8/5表明,35≈28,循环长度应为5.实际上恰存在长度为5的循环(4,6,
9,7,5).
   渐进分数19/12表明,312≈219,循环长度应为12,实际上恰存在长度为12的循环
(44,66,...59).
   这四个渐进分数的分母与实际存在的循环长度的一致性,给了人们一些启发与信
心,促使人们继续考虑:是否存在长度为 41,53,306,665,15601,...的循环?令人遗
憾的是,已经证明长度是41,53,306的循环肯定不存在,那么,是否会有长度为 665,
15601,...的循环呢?
   F迭代与G迭代究竟能有哪些循环呢?人们正在努力探索中!


--
千 但 此 月 人 别 何 不 照 低 转 何 起 高 又 我 今 不 把 明 
里 愿 事 有 有 时 事 应 无 绮 朱 似 舞 处 恐 欲 夕 知 酒 月 
共 人 古 阴 悲 圆 长 有 眠 户 阁 在 弄 不 琼 乘 是 天 问 几 
婵 长 难 晴 欢    向 恨          人 清 胜 楼 风 何 上 青 时 
娟 久 全 圆 离                   间 影 寒 玉 归 年 宫 天 有 
         缺 合                            宇 去    阙       

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