联系电话  13611276845
【原】Hailstone序列的研究
浏览数:6137   发布时间:2018-1-26
Hailstone,2进制

Hailstone Sequence问题是一个著名的数学问题,至今没有证明其正确性,也没证明其是错误的,即任何一个正整数N,如果是偶数的话就÷2,如果是奇数的话就×3+1,最后这个数都会变为1

代码如下:

    while( n > 1 )

    {

        if ( n & 1 )

            n = n + ( n >> 1 ) + 1; // n = n*3 + 1

        else

            n = n>>1; // n = n/2

    }

拿 n = 15 举例:

15:         1111 ---- 2进制1111在*3+1的过程中很容易就产生了10的情况,而一旦0产生,就不容易被抹去。
46:       101110
23:       10111  ---- 结尾是1的,在*3+1的过程中,结尾会产生0,然后就被抹去
70:     1000110
35:     100011
106:   1101010
53:    110101    --- 2进制数中带有0101的数,很容易在*3+1的过程中变成00000的情况
160: 10100000    --- 这类结尾全是0的,会直接被抹去,最终变成101
80:  1010000
40:  101000
20:  10100
10:  1010
5:   101
16:10000
8: 1000
4: 100
2: 10
1: 1

根据从2进制分析,

1) 结尾是0的直接被抹去

2) 结尾是1的,在*3+1的过程中,结尾又产生了0,又会被抹去

3)在*3的过程中,整个2进制数串会产生1010这样的形式,然而1010这样的形式在*3+1的过程中是活不久的,所以避免不了被抹去的命运。


综上所述:虽然n在整个变化过程中,看起来 ×3+1 比 ÷2 会使数字变得更大,但架不住 ÷2的次数比 x3+1要多,所以n只能是越来越小,最终走向1.

所有评论
匿名  2019-3-5 10:38:25 :
很有意思的算法
姓名:
留言:
验证码:
验证码,看不清楚?请点击刷新验证码
 
用户登录
用户注册

通讯地址:北京市丰台区贾家花园15号院7号楼一层西侧(东铁匠营企业集中办公区)

联系电话:13611276845 联系QQ:71828625; 11919874

©2012-2023 uscube.com 版权所有 京ICP备18038096号-1

营业执照 京公安备11010602006327号