## 用户名 Email 自动登录 找回密码 密码 立即注册
 搜索

# 第70期源码[acme_pjz VS X0oo] [复制链接] 发表于 2011-4-18 19:43:07 | 显示全部楼层
 本帖最后由 XOoo 于 2011-4-18 20:15 编辑 回复 Igawk 的帖子 刚再仔细想来一下，发觉很有问题哈，真对不起啊大家！ 证明过程（有些步骤不知道怎么描述哈...将就一下...） 原函数改为等价的形式: f(X) = IIf(X And 1, (X * 3 + 1) / 2, X / 2) 定义一种描述方式：Fn(X)，代表连续进行n次函数运算。如F3(X)=F(F(F(X))) 设H和L分别是X的高m位和低n位: X = H + L 定义函数: F(H, L) = IIf(L And 1, H * 3 / 2 + (L * 3 + 1) / 2, H / 2 + L / 2) [  即F(H, L)=f(H + L)  ] 再在F()的基础上定义函数FH()、FL()： F(H, L)=FH(H, L)+FL(L, L)，其中 FH(H, RND) = IIf(RND And 1, H * 3 / 2, H / 2) FL(L, RND) = IIf(RND And 1, (L * 3 + 1) / 2, L / 2) 对于任意一个正整数K显然有： FH(K,RND)<=FL(K,RND) 进一步可以推出，对于任意随机数列RNDi，有（这一步不会用数学的语言说明,可能是有问题的）: FHn(K, RNDi) <= FLn(K, RNDi)  ,i=1...n 且当数列RNDi满足 FLn(K, RNDi) <= K   ,i=1...n 有FHn(K, RNDi)  <= K 当满足上式时（注意FH是只由乘法构成的函数,FHn(K, RNDi)等价于K乘以一个未知数#）,对于任意的其它正整数A都有 FHn(A, RNDi) <= A  ,i=1...n 对于原命题，当 fn(X) < X = H + L 有等价的形式： fn(X) = Fn(H, L) = FHn(H, L) + FLn(L, L) < H + L 而当 FLn(L, L)< L 时， 必然满足 FHn(H, L)< H 所以 FLn(L, L) + FHn(H, L) < H + L

### 点评 发表于 2011-4-18 21:26:19 | 显示全部楼层
 来看看这个…… 发表于 2011-4-18 22:37:37 | 显示全部楼层
 [ 本帖最后由 acme_pjz 于 2011-4-18 22:39 编辑 ] 维基百科上面不是有么：http://en.wikipedia.org/wiki/Collatz_conjecture#Optimizations Optimizations ==================================================================== The As a parity sequence section above gives a way to speed up simulation of the sequence. To jump ahead k steps on each iteration (using the f function from that section), break up the current number into two parts, b (the k least significant bits, interpreted as an integer), and a (the rest of the bits as an integer). The result of jumping ahead k steps can be found as: f^k(a 2^k+b) = a 3^c[b]+d[b]. The c and d arrays are precalculated for all possible k-bit numbers b, where d [b]is the result of applying the f function k times to b, and c [b]is the number of odd numbers encountered on the way. For example, if k=5, you can jump ahead 5 steps on each iteration by separating out the 5 least significant bits of a number and using: c [0...31] = {0,3,2,2,2,2,2,4,1,4,1,3,2,2,3,4,1,2,3,3,1,1,3,3,2,3,2,4,3,3,4,5} d [0...31] = {0,2,1,1,2,2,2,20,1,26,1,10,4,4,13,40,2,5,17,17,2,2,20,20,8,22,8,71,26,26,80,242}. This requires 2^k precomputation and storage to speed up the resulting calculation by a factor of k (see space-time tradeoff) For the special purpose of searching for a counterexample to the Collatz conjecture, this precomputation leads to an even more important acceleration which is due to Tomás Oliveira e Silva and is used in the record confirmation of the Collatz conjecture. If, for some given b and k, the inequality f^k(a 2^k+b) = a 3^c[b]+d[b] < a 2^k+b holds for all a, then the first counterexample, if it exists, cannot be b modulo 2^k. For instance, the first counterexample must be odd because f(2n) = n; and it must be 3 mod 4 because f^3(4n+1) = 3n+1. For each starting value a which is not a counterexample to the Collatz conjecture, there is a k for which such an inequality holds, so checking the Collatz conjecture for one starting value is as good as checking an entire congruence class. As k increases, the search only needs to check those residues b that are not eliminated by lower values of k. On the order of 3^(k/2) residues survive. For example, the only surviving residues mod 32 are 7, 15, 27, and 31; only 573,162 residues survive mod 225 = 33,554,432. 其中f(k)=k/2如果k是偶数，(3k+1)/2如果k是奇数，f^n表示f迭代n次…… 发表于 2011-4-19 10:05:18 | 显示全部楼层 提示: 作者被禁止或删除 内容自动屏蔽 回复 发表于 2011-4-19 15:23:11 | 显示全部楼层
 学习一下源码。 发表于 2011-4-20 15:47:36 | 显示全部楼层
 本帖最后由 XOoo 于 2011-4-20 15:48 编辑 总算又闲下来了，刚看过acme_pjz的代码，好些处理方法我没想到，学习了～ :clap: 我也投了acme_pjz一票 发表于 2011-4-20 17:05:51 | 显示全部楼层
 acme_pjz 也算是老法师了。XOo。 比较认真，投他一票 发表于 2011-4-20 23:35:57 | 显示全部楼层
 下来研究研究 发表于 2011-4-23 16:44:17 | 显示全部楼层
 恩。看看。学习下 发表于 2011-4-25 18:53:55 | 显示全部楼层
 学习学习，看看先

 您需要登录后才可以回帖 登录 | 立即注册 本版积分规则 回帖并转播 回帖后跳转到最后一页

GMT+8, 2022-7-1 04:28

VB爱好者乐园(VBGood)