叶承汾论3X+1

第3卷 第 1期 2004年 1月 北京工业职业技术学院学报 JOUKNALOFBELIINGVOCATIONAL&~CI-LNICAL INSTI1UrEOFIN1)USTRY No．1 Vo1．3 J an 2004 论 3 x+1 问 题 叶承汾 (北京工业职业技术学院，北京 100042) 摘 要：本文运用三种不同的数学方法，论及 3x+1问题整体性质的三个方面：(1)利用柯拉茨函数的反函 数，构造了全体C数列复杂的树状结构；(2)借助奇数的划分，提供了相邻两奇数增幅的分布律和等价总增 幅；(3)对于a)(+1问题，应用不定方程，证得其相邻两奇数增幅的数学期望在奇数 a>3时大于 1。 关键词：柯拉茨函数；奇数的划分；不定方程 中图分类号 ：0156．1 文献标识码 ：A 文章编号：1671—6558(2004)01—23—08 On “3x-4-l”question Ye Chengfen (Beijing Vocational& Technical Institute of Industry，Beijing 100042，China) Abstract：This artcle in virtue of different mathematical methods of three kind．treats of three sides of unitary property about“3x+1”question：(1)Constructed intricate and dendriform frame of total C rebuke in virtue of inverse function of L．Co llatz’S function；(2)Provided two conterm inous impar am plitude’S distributing and total am plitude of equivalence in virtue of impar partition；(3)Proved two conterm inous impar am plitude’S mathematical expectation>1(a>3)about“ax+1”question by using diophantine equation． Key words：L．Co llatz’S function；impar partition；diophantine equation 引言 当代，有一个风靡世界的“3x+1”问题，人人都 会演算，但要证明它却像对付坚硬的盘石，它似乎能 轻而易举地挫去人们智慧的锋芒。_2 J (1)问题的由来 从上世纪 50年代开始，国际数学界广泛流传着 如下一道有趣的数学问题：任意给定一个自然数 X， 如果是偶数，就变换成 X／2；如果是奇数，则变换成 3X+1。对 自然数的上述变换，实际上是进行下列 函数的迭代 c㈦={ 。 ； 50多年过去了，所有人都得出相同的结论：“从 任意一个 自然数开始，经过有限次迭代，最终得到 1”。例如，从 5开始的迭代过程是：5，l6，8，4，2，1。 Et本东京大学的本田信夫已对 240，大约是 11000亿 以下 自然数 做 了检 验，1992年利 温斯 (G．T． Leavens)和佛穆兰(M．vermeulen)也对小于 5．6× l0 的自然数进行了验证，均未发现反例。 “3x+1问题”流传之广、名 目繁多是空前的。 由于柯拉茨(L Collatz)在 1950年召开的一次国际 收稿 日期：2003一O9一O7 作者简介：叶承汾(1948一)，男，阜新矿业学院矿山测量专业毕业，高级讲师。 维普资讯 http://www.cqvip.com 24 北 京 工 业 职 业 技 术 学 院 学 报 第 3卷 数学家大会上谈起过这一问题，因此许多人称之为 “柯拉茨 问题”。1952年英 国数学家斯韦茨 (B． Thwaites)又独立地发现了这个问题。几年之后，这 个问题再次被俄 克拉 荷大学 的安德烈 (R．V． Andree)所发现。在问题流传过程中，因为柯拉茨的 同事汉斯、美国数学家乌拉姆、日本数学家角谷静夫 都研究过它，所以柯拉茨问题又称汉斯算法、乌拉姆 问题、角谷猜想。为了避免问题的归属引起争议，许 多文献称之为“3x+1问题”。 (2)问题的难度 对于数 X进行 C迭代所得到的数列称为数 x 的C数列，问题的复杂性首先表现在 C数列中各项 大小的不规则性，时大时小、神奇莫测、变幻无穷。 问题的复杂性还表现在数 rl的迭代峰值上，所 谓数 n的迭代峰值就是 n的C数列中的最大值，记 作 d(n)。关于迭代峰值有一个有趣的现象：有些峰 值很少出现，有些峰值频繁出现。最引人注意的峰 值是 9232，在前 1000个 自然数的迭代中，峰值为 9232的超过 350个，有时多个连续自然数的峰值都 是 9232。在前 n个自然数的迭代峰值中，必有最大 者，称为最大峰值，记作 D(N)，最大峰值要比N值 增长快得多，1978年克兰多尔(R．E．Crandal1)从理 论上证明了，随着奇数 rn的增大，D(m)／m可为任 意大。 问题复杂性的另一种表现是 C迭代的路径长。 对任一自然数 x进行 C迭代第一次出现 1所经历 的迭代次数，称为 C迭代的路径长。C迭代的路径 长时长时短，难以捉摸。 尽管如此，人们普遍认为：在 C迭代的过程中， 一 旦出现2的幂，问题就解决了，而 2的幂有无穷多 个，只要迭代过程持续足够长，必定会碰到一个 2的 幂使问题得以解决。正是这种信念使得问题每到一 处，便在那里掀起一股“3x+1问题”狂热。⋯ 本文以下论及 3x+1问题整体性质的三个侧 面：(1)C数列的树状结构；(2)c迭代过程中相继两 奇数增幅的分布律和等价总增幅；(3)广义 C迭代 过程中相继两奇数增幅的数学期望。 1 C数列的树状结构 1．1简化柯拉茨函数的反函数 令 e(x)为 3x+1所含的素因数 2的个数，对简 化柯拉茨函数 C(x)=(3x+1)／2 ( ，x--=l(mod2) 取其反函数得：D(x)：1／3(X·2“一1) 其中n等天原函数 C(x)中的e(x)，有如下论断 成立， 定理 1简化柯拉茨函数的反函数 D(x)具有如 下性质： (1)D(x)的定义域为：)c三1(砒 )，)c三1，2(n~d3) (2)当 x三1(mod3)时，n=2k， D(x)：1／3(x·22 一1) (k=1，2，3⋯⋯)(1) 当x=2(mod3)时，n=2k一1， 【)(X)=1／3(x·2 ～一1) (k=1，2，3⋯⋯)(2) (3)D(X，k+1)=4D(X，k)+1 (k=1，2，3⋯⋯) (3) 证明：(1)若 x~0(rood3)， ‘ ．’3D(X)+1=X·2 ， ． ‘ ．3D(X)+1三1(mod3)， X·2“=0(rood3)，矛盾 ， ． ‘ ． x=--0(mod3)时，D(x)不存在。 (2)当x三1(mod3)时， ‘ ．‘D(x)=1／3(x·4n 一1) 其中(n一1)／2为任意自然数， 设为 k=n／2，则 n=2k， 因而有 D(x)=1／3(x·2 一1) (k=1，2，3⋯⋯)； 当x=2(mod3)时 ‘ ．‘D(x)=1／3(2x·2 一 一1) =1／3(2x·4(n～)／2—1) 其中(n一1)／2为任意自然数， 设为 k一1=(n一1)／2，贝0 n=2k一1， 因而有 D(x)：1／3(x·2 一 一1) (k=1，2，3⋯⋯)； 显然，D(x)也与k有关， 用 D(X，k)记之， 例如：当x三1(mod2)，x三1(mod3)， k∈N时，D(X，1)：1／3(4x一1)， D(1，1)=1 D(1，2)=5，D(7，1)=9，等等。 (3)当x三1(rood3)时， 4D(x，k)+1=4·[1／3(x·2 k一1)]+1 =1／3(x·22(k 1)一1) =D(x，k+1)； 当x--=2(mod3)时，4D(X，k)+1= 4．[1／3(x·2 k～一1)]+1 =1／3(x·22(k 1)一l一1) =D(X，k+1)； 1．2 C数列的树状结构 利用简化柯拉茨函数的反函数 D(x)的性质，可 维普资讯 http://www.cqvip.com 第 1期 叶承汾：论 3x+1 问 题 25 构造 C数列如下的树状结构： (Al11，Al12⋯) 无 (A131，A132⋯) ⋯ (All， A12， A13 ⋯) A1 其中，A =1 (Al1，A12，A13⋯)=(5，21，85，⋯) (A1l1，A112，⋯)=(3，13，53，⋯) (A131，A132，⋯)=(113，453，1813，⋯) 利用简化柯拉茨函数的反函数 D(X)的性质和 C数列的树状结构图，可以解释 C数列的一些现象。 例 1、迭代路径长为 1的奇数，即经一次 C迭代 后为 2的幂的奇数 对于简化柯拉茨函数，迭代路径长为1的奇数，即 是在(1)式中令x=1，得I3(1，k)= 1(4 —1) (kEN) 即，X={(4“一1) 由于此类奇数相邻两数的间隔为：Xn+1一X = 1 。 (4n 一1)一 1(4n一1)：4n ，所 以，随着 x的增 大，此类数越来越稀，迭代过程中碰上2的幂的机会 随着 X值的增大而减少，所以，多数的 C数列是“反 复迭代，逐渐下降”的。 例 2、1至25的奇数的简化C数列 1至25的奇数的简化C数列为： 按其内部规律排列成树状结构如图 1所示，大 于25的数括在括号内，符号一表示同一层次如 5， 21，85均迭代至 1；7，29均迭代至 11，为清晰起见省 略了许多同层次的数，如 11同层次的数为：11，45， 181，等等。 (33) 25 9 19 7 — 29 11 17 3 — 13 — 5 — 21 1 一 (101) ⋯ 15 23 一 (93) ⋯ (35) (53) 一 (213) ⋯ 一 r85) ⋯ 图 1 1至25的奇数的位置 如果加入偶数，其结构更为复杂，如下图所示。 括号中的数是奇数，偶数加于其中并在一定的地方 生出枝权。此图权是极小一部分。 ‘ ． 212 (17) 104 106 52 (53) 320 26 160 (13) 80 40 (3) 20 (21) 128 10 64 (5) 32 16 8 4 2 (1) 图 2 奇数树干上附加偶数树权 2 C迭代过程中相继两奇数增幅的分布律和等价总 增幅 2．1等差数列的对分 对任意的等差数列 at+b(t∈N)，都可对分为 两个数列：2at+b，2at h-ah-b。 2．2奇数的划分 对全体奇数一分为二，留下一半，再将其余一半 一 分为二；再留下一半，将另一半一分为二，直至无 穷，称为对奇数的划分。用大括号表示对分，用 *号 表示留下的一半，具体划分如下： * f 16t h-5··· I 16t h-l3* 5 3 1 1 1 7 5 5 5 1 3 3 3 1 1 1 5 5 1 5 1 " ¨ ● 5 1 7 3 3 5 9 5 1 1 7 1 5 2 1 1 3 1 3 5 7 9 ¨ " 1 3，必存在某个正奇数 r，使得 r的广义C迭代： C(z)= (口。r+1)／2 不出现 1。 1978年克兰多尔证明，当a=5、181、1093时上 述猜想是正确的；另有人研究过 7x+1问题，对 r= 3的迭代项数已超过 10 。o。，仍看不到任何重复的迹 象。克兰多尔的证明主要是找到 1以外的其它循 环。对于 a的其余所有奇数值，寻找其它循环或者 证明没有其它循环都是十分困难的。本文是要证 明：当a>3时，C迭代过程中相继两奇数增幅的数 学期望大于 1。 3．1广义 C迭代过程中相继两奇数的增幅 3．1．1增幅约为 a／2的奇数 设 a=2k+1，解不定方程 ax+1=2y 且满足 xzy~l(mod2) 解 ：显然 ax三1(rood2)’．‘a三1(rood2) ． ’ ．x三1(mod2)，将 X对分，当X=4t+1时， y_-1／2(4at+a+1)=2at+k+1， 为使 Y为奇数，必须 k--=O(mod2)； 当x=4t+3时，y=1／2(4at+3a+1)=2at+3k+2， 为使 y为奇数，必须 k三1(mod2)；所以， k=O(mod2)时 ，X=4t+1，Y=2at+k+1 k三1(mod2)时，X=4t+3，Y：2at+3k+2 为不定方程的解。 3．1．2增幅约为 a／4的奇数 设 a=2k+1，解不定方程 ax+1=4y 且满足 x三y三1(mod2) 解：显然 axe=3(rood4)．’．(2k+1)x=3(mod4)， 对相同的模 rood4，经计算： 当 k=O或 k三2时，a三1，x三3，．‘．X=4t+3 当 k三1或 k三3时，a=3，x三1，．’．X=4t+1 将 4t+1、4t+3分别对分为 8t+1、8t+5和 8t +3、8t+7后讨论如下： ①设 X=8t+1，贝0 Y=1／4(8at+a+1) =2at+1／2(k+1)，为使 Y为奇数， 需 k三1(rco：g)，即 k=4n，此时 y=2at+2n+1； ②设 X=8t+5，贝0 Y=1／4(8at+5a+1) =2at+1／2(5k+3)，为使 y为奇数， 需 I (眦d4)，即k=4n+3，此时 y=2at+10n+9； ③设 x=8t+3，贝U Y=1／4(8at+3a+1) =2at+1／2(3k+2)，为使 Y为奇数， 需 k三三0(m )，即 k=4n，此时 y=2at+6n+1； ④设 X=8t+7，贝0 Y=1／4(8at+7a+1) =2at+1／2(7k+4)，为使 Y为奇数， 需 k三 2(HDd4)，即k=4n+2，此时 y=2at+14n+9； 综上所述，当 k三1(n )时，X=8t+1，y=2at+2n+1； k----2(~ )时，x=8t+7，y=2at+14n+9； k三3(n )时，x=8t+5，y=2at+IOn+9； k三三1)(n )时，x=8t+3，y=2at+6n+1， 为不定方程的全部解。 3．1．3增幅约为 a／8的奇数 设 a=2k+l，解不定方程 ax+1=8y 且满足 x三y三1(mod2) 解 ：显然 ax=7(rood8)．‘．(2k+1)x=7(rood8)， 对相同的模mod8下，经计算： 当 k三1或 k--=5时，a=3，x=5，．‘．X=8t+5 当 k三2或 k=6时，a=5，x=3'．．．X=8t+3 当 k=3或 k三7时，a三7，x三1，．’．X=8t+1 当 k=4或 k三0时，a三1，x三7，．’．X=8t+7 将 8t+5、8t+3、8t+1、8t+7分别对分后讨论 如下： ①设 X=16t+5，贝0 y=1／8(16at+5a+1) = 2at+1／4(5k+3)，为使 y为奇数， 需 k-=-----5(n~dS)，即 k=8n+5，此时 y=2at+IOn+ 7： ②设 x=16t+13，贝0 Y=1／8(16at+1la+1) =2at+1／4(13k+7)，为使 Y为奇数， 需 l 1(m]d8)，即k=8n+1，此时 y=2at+26n+5； ③设 x=16t+3，贝0 y=1／8(16at+3a+1) = 2at+1／4(3k+2)，为使 Y为奇数， 需 k-=-6(n~dS)，即k=8n+6，此时 y=2at+6n+5； ④设 X=16t+11，贝0 Y=1／8(16at+11a+1) =2at+1／4(1lk+6)，为使 Y为奇数， 需 k三 (nD(i8)，即 k=8n+2，此时 y=2at+22n+7； ⑤设 X=16t+1，贝0 Y=1／8(16at+a+1) =2at+1／4(1／+1)，为使 Y为奇数， 需 k三_3(nD(i8)，即k=8n+3，此时 y=2at+2n+1； ⑥设 X=16t+9，贝U Y=1／8(16at+9a+1) =2at+1／4(9k+5)，为使 Y为奇数， 需 k----7(n~dS)，即k=8n+7，此时y=2at+18n+17； ⑦设 x=16t+7，贝4 y=1／8(16at+7a+1) = 2at+1／4(7k+4)，为使 Y为奇数， 需 k--=O(n~dS)，即 k=8n，此时y=2at+14n+1； 维普资讯 http://www.cqvip.com 北 京 工 业 职 业 技 术 学 院 学 报 第 3卷 ⑧设 X=16t+15，贝0 Y=1／8(16at+15a+1) =2at+1／4(15k+8)，为使 Y为奇数， 需l 珥(眦趱)，即k=8n+4，此时y=2at+30n+17； 综上所述 ，当 k三1(mod8)时，X=16t+13， Y=2at+26n+5： k三2(mod8)时，X=16t+11， Y=2at+22n+7： k~3(mod8)时 ，x=16t+1， Y=2at+2n+1： k~4(mod8)时 ，x=16t+15， Y=2at+30n+17． k~5(mod8)时，X=16t+5， Y=2at+IOn+7． k三6(mod8)时，X=16t+3， Y=2at+6n+5． k~7(mod8)时，X=16t+9， Y=2at+18n+17． k~O(mod8)时，X=16t+7， Y=2at+14n+1． 为不定方程的全部解。 3．2广义C迭代过程中相继两奇数的增幅 3．2．1满足不定方程 ax+1=2y 相继两奇数的增幅：y x a2 +zl x > z a 3．2．2满足不定方程 ax+1=4y 相继两奇数的增幅：专=号+ >号 3．2．3满足不定方程 ax+1=8y 相继两奇数的增幅：专 专+ lx>a 3．3满足不定方程 a)(+1=2ny (n=1，2，3)的奇数 的划分 为求得a)(+1问题在广义C迭代过程中相继两 奇数增幅的数学期望，利用 3．1的结果，验明满足不 定方程 a)(+1==2ny (n=1，2，3)的奇数的全部 划分如下： ①当k~l(mod8)时，全体奇数划分为： 2 』4t十1 l4t+3* 『4t+1* 2 + 1 4t+ J 8 +3{．1o，t+．13一* l 4t+3 I 十 * l L8t+7* ③当k~3(mod8)时，全体奇数划分为： I f I 16t+1* ． I 4t+1J 8 +9．一 2t+1J+1 叭¨ ⋯ I l8t+5* I4t+3 ④当k~4(mod8)时，全体奇数划分为： 4t+ 1 『 f8t+1* 2t+ 1 4 + 18t+5．。166 t++5。3*⋯ 【4t+3* ⑥当k~6(mod8)时，全体奇数划分为： 『4t+1* 2t+it 8t+3{16t+3 l 4t+ I 16t+11⋯ l L8t+7 ⑦当k~7(mod8)时，全体奇数划分为： f f f 16t+1⋯ ， ．I 4t+1J 8 +9* 2t+1l+1 I l 8t+5* I4t+3 ⑧当k~O(mod8)时，全体奇数划分为： 4t+ 1 I f 8t+3 2t+1 l l 4t+ f 16t+7* l 8t+7 l6t+15⋯ 3．4广义 C迭代过程中相继两奇数增幅的数学期望 定理 5：广义 C迭代过程中相继两奇数增幅的 数学期望 E(∈)> Da 综合以上各种情况，ax+1问题在广义 C迭代 过程中相继两奇数增幅的分布律为： 为 分 划 撇 + + 本 t t ． 3 7 时 譬 + 乱 三 ● k + 当 ⑤ 维普资讯 http://www.cqvip.com 第 1期 叶承汾：论 3x+1 问 题 29 S >号 >号 >詈 ⋯ P ⋯ 2 4 8 数学期望为：E(s)=∑siPi> a+ a+ a= 5a 显然，当a>3时，E(S)>1。 4实例 4．1 3x+1迭代程序 以下 Mathmatica程序可快速求出自然数经 3x +1迭代所生成的C数列。 a[1]=k=27；b=112； For[i=1，i<=b，i++， If[FlOOr[k／2]一k／2==0， ali+1 J=ali J／2， a[i+1]=3 a[i]+1]；k=a[i+1]] A=Table[a[i]，{i，l，b，l}]； Print[A] 其中，k为选取的自然数，b是路径长，适当调整 后使最后一个值为 1。 4．2相邻两奇数增幅的统计 4．2．1具有最大路径长的奇数 在文献[1]最大路径长的

资料

新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单

中(第 15页，表 3)选取 6个奇数的统计资料如下。 X=27 E(S)=1．104 等价总增幅 r=0．919791 X=871 E(S)=1．092 等价总增幅 r=0．900862 X=2223 E(S)=1．117 等价总增幅 r=0．89006566 X=6171 E(S)=1．091 等价总增幅 r=0．918625 02 X=35655 E(S)=1．091 等价总增幅 r=0．915097 增幅S 3／2 3／4 3／8 3／16 3／32 3／64 3／128 个 数 概 率 67 0．563 31 0．261 13 0．109 5 0．042 ’ 0．017 1 0．008 维普资讯 http://www.cqvip.com 北 京 工 业 职 业 技 术 学 院 学 报 第 3卷 X=52527 E(∈)=1．115 等价总增幅 r=0．91571125 4．2．2形如 2 一1(k>1)的奇数 1978年克兰多尔(R．E．Crandal1)证明，2 一1(k>1)的奇数在其前 2k项中，相邻两奇数一直是增加的， 此类数的 C数列中相邻两奇数的增幅是如何分布的呢? X=2加一1=1023 E(∈)=1．004 等价总增幅 r=0．6997752o X=220—1=1048575 E(∈)=1．035 等价总增幅 r=0．79496561 5结论 (1)由于简化柯拉茨函数反函数的多值性，形成 了C数列复杂的树状结构，并且全体偶数成为附在 奇数主干上的枝权，加剧了 C数列的复杂性和其规 律的隐蔽性。 (2)当自然数足够大时，简化 C数列C(x)=(3x +1)／2e(x)相邻两奇数增幅的数学期望趋向 1，等价 ， 、k 总增幅为l )，所以，x反复k(k一∞)次迭代的效 果，相当于每次降幅为 3／4的 k次下降。无论多大 的自然数，迭代迟早会降至 1。 (3)当自然数足够大时，广义 C数列 C(x)=(ax C +1)／2 相邻两奇数增幅的数学期望大于 ，所 以，当a>3时，至少存在一个奇数 r，它的广义C数 列无限增大，始终不能降至 1。 (4)可以较自然地推测，广义 C数列 C(x)=(a)( +1)／2 ( ’相邻两奇数增幅的数学期望为：寻，等价 总增幅为：(号) 参考文献： [1]贺贤孝．数学中的未解之谜[M]．长沙：湖南教育出版社， 1998 [2]徐品方．引无数英雄竞折腰的 3x+1猜想[J]．数学通报． 2002(1) [3]华罗庚．数论导引[M]．北京：科学出版社，1979 [4]潘承洞，潘承彪．初等数论[M]．北京：北京大学出版社， 1992 (责任编辑：郭振海) 维普资讯 http://www.cqvip.com