3n 1问题 虽然很多文章提到 但是这里还是简单的说一下它的运算过程 任意一个大于0的整数 (1)假如它是偶数 则除以2 (2)假如它为奇数 则乘以3再加1 不断重复这两种操作 最后必将得到数字1。用python 实现的算法就是 def collatz(n): if n 0: print( 初始值 ,n, 不符合条件 );return while n ! 1: print(n) if n%2 0: # (1) n n//2 elif n%2 1:# (2) n n*3 1 print(n) 不用担心程序停不下来 因为没人 can 证明这个猜想不成立 至少我都没有碰到某个死循环。假如去掉“等于1”的判断条件 把1放进程序算一下 def test(n): ct 50 while True: print(n) if n%2 0: # (1) fa n n//2 elif n%2 1:# (2) fb n n*3 1 ct- 1 if ct 0:break#test(1) 可以看出程序是在整数1这里不断打圈圈的 1 奇数 4 偶数 2 偶数 1 》》》 因此1是个黑洞 程序掉进去就出不来了。严格来说 这个黑洞是由1 4 2 这3个整数 3点环 构成的。因此collatz 在 1 这里做了个踩刹车动作 结果结论就像是总会得到 1 的最终结果。完整的事实是得到一个 1 4 2 构成的三角形旋转黑洞...闲话就此打住 下面继续讨论第一个程序的算法问题.这个算法的流程控制 是由数值的奇偶性控制的。也就是说整个过程的暂态结果 处于奇数和偶数交越状态之中。当暂态结果是偶数时 它将由第(1)分支处理 直到变成奇数。当暂态结果是奇数时 它将由第(2)分支处理 直到变成偶数。为了凸现奇偶性之间的转变 我们可以把分支 1 提取出来 主要用于实现从偶数到奇数的状态转变 新建一个辅助函数 提取某个整数因子 def abstr(n,mod 2):# m 是要提取的因子 n kore * (m ** time) time 0 # 次方 kore n # 核 while kore%mod 0 and kore 0 : kore kore//mod time 1 return kore,time 现在改写原来的collatz函数,这样打印的出来的数字会少一些 def collatz_abstr(n): if n 0: print( 初始值 ,n, 不符合条件 );return while n ! 1: print(n) if n%2 0: # (1) n abstr(n)[0] elif n%2 1:# (2) n n*3 1 print(n) #collatz_abstr(27) 事实上collatz猜想 等价于 把任意一个大于1 奇数数丢进程序 最终都会得到 1这个结果。因为分支 1 总会把偶数变成奇数 也就是不断抽取2这个因子后得到的核 也就是初始值是偶数并不重要 它将变成奇数核。因此这个猜想只需考虑 任意奇数最终转换成 1 就行了。要想观察数列 可以开始观察一下 奇数核时观察一下 最终结果观察一下 def collatz_abstr(n): if n 0: print( 初始值 ,n, 不符合条件 );return print(n) while n ! 1: if n%2 0: # (1) n abstr(n)[0] print(n) elif n%2 1:# (2) n n*3 1#collatz_abstr(27) 下面考虑一个符合条件的奇数q的转变过程 q奇数 - 3*q 1 2*q q 1 偶数 - q (q 1)/2 未知。现在设q 被分成 大b小a两部分 且满足 a b q, b-a 那么 a (q-1)/2 a 为小半部 b (q 1)/2 b 为大半部 那么 上面 q (q 1)/2 未知 (a b) b 2b a 3b-1 3a 2 它的奇偶性取决于 a。即[1]若a 为奇数 则 q - 2b a 是一个奇数 且大于 q( b [2]若a 为偶数 则q - 2b a 是 偶数,然后可以除以2 - b a/2 3a/2 1 且小于 q 。从[2]可以推导出一条公式 一个初始奇数q,若表达成k*(2^n)-1的形式(其中k是奇数,n 1) 那么会到达一个暂态结果k*3^n-1.q k*(2^n)-1 q - k*3^n-1进一步推导 会有如果 q k*(3^m)(2^n)-1 会到达一个暂态结果 (k*3^(m n)-1)/2,其中k是奇数,n 1。这个公式也可以看出 好多初始值不同整数被“简并”到同一个暂态结果上了。假如你下过飞行棋 那么这就像投到好的色子点数 在空中直接越过许多区域。‘’‘‘ def fast(q): v q 1 k,n abstr(v,mod 2) k,m abstr(k,mod 3) v (k*3**(n m)-1)//2 return v 现在把这个快速的暂态放进collatz的第二分支 print( ----hh-- )def collatz_abstr(n): if n 0: print( 初始值 ,n, 不符合条件 );return print(n) while n ! 1: if n%2 0: # (1) n abstr(n)[0] print(n) elif n%2 1:# (2) n fast(n)#collatz_abstr(27) 假如你的运气特别好 初始值是2^n 那么这个函数一路到底,运气次好一点的就是那些一步可以到2^n的奇数,那么是哪些奇数 由 3*q 1 2^n 得 q (2^n-1)/3 很明显不是所有的2^n都可以整除以3 但是所有 2^(2*n)-1 可以。n 1 def goodluck(n,show 1): if show 1: for i in range(1,n): v (4**i-1)//3 print(i,v) else: v (4**n-1)//3 return (v)#goodluck(10) 假如把这些数转换为二进制数 你会看到奇特的现象 都是零一相间的数,这样它的小一半加上它再加一就是4^n次方 n 10for i in range(1,n):# 虽然 1 可以变成4 但是触碰了collatz的底线 根据前面的讨论 会落入循环 v goodluck(i,show 0) a (v-1)//2 # v 2a 3a 2 v a 1 v bin(v) a bin(a) print( v {0: 20} .format(v[2:])) print( a {0: 20} .format(a[2:])) print( ----- ) 我们知道 “整数”这个概念是对“奇数”和“偶数”这两个概念的简并 假如把整数分成奇数和偶数 那就是一种细分结构。那么再把奇偶细分 可以得到更细的概念。因为奇偶代表着两态 n%2 1 为奇 n%2 0 为偶。假如我们把整数当成四态的数 类似地 n%4 1 为1态 称 n 为1态数 或a数 n%4 2 为2态 称 n 为2态数 或b数 n%4 3 为3态 称 n 为3态数 或c数 n%4 0 为0态 称 n 为0态数 或d数 那么这时的整数性质就成为 四态性质 不再是奇偶性质 当然 此时也可以讨论奇偶性 不过会发生简并 四态的运算性质和奇偶运算性质类似 不过框架不同了。比如 1态数 1态数 变成 2态数 如 5 5 10 5是1态数 10是2态数。又比如 3态数 x 3态数 变成 1态数, 如 3*7 21这些性质可以由同余理论推导。那么现在回到collatz上面来 前面我们说它的流程由奇偶行控制 那么,现在由4态性控制。假如要让程序能够运行下去 那么该如何改写呢 为了方便表达 我们把整数转换成4态数数列 每个整数 正的 由它的态和“态中索引位置”决定 如下 真值 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,态值 d0, a0,b0,c0,d1,a1,b1,c1,d2,a2整数9就是a3,即a态里排第三 按照列表的记法 可以写成a[3]。在collatz变换下 每一次“可推测”的态性变化规律如下 c[i] - a[i j] j (i 2)/2, 其中 i 为偶数。↑ *3 1 2 c[i] - c[i j] j (i 1)/2, 其中 i 奇数。 ↑ *3 1 2 a[i]- d[i j], j (i 1)/2, 其中 i 为奇数。↑ *3 1 2a[i]- b[i j], j 1/2 其中 i 为偶数。 ↑ *3 1 2b[i]- a[j], j i/2, 其中 i 偶数。 ↓ 2b[i]- c[j], j (i-1)/2, 其中 i 为奇数。 ↓ 2d[i]- abstr(i)- kore - a c ↓ #如果 i%4 1,转化成 a[j],j (i-1)//4 #如果 i%4 3 ,转化成 c[j], j (i-3)//4 #如果 i%4 2, m i//2, 又 #如果m%4 1 转化成 a[m//4] #如果m%4 3 转化成 c[m//4] #如果 i%4 0: - d[i//4]def what_is_the4(n):# 一个整数属于哪个态及索引 states dabc st states[n%4] i n//4 return st,i 有意思的是 d[i]在向a和c转换时 形成一种周期自相似结构。比如以4为周期打印转换关系 则右边的dom和原来的dom一样。d[i]的collatz转换 在映射上形成分形结构。假如用分形的角度分析 那么“态数”是尺度。再假如参考物理术语 那么索引位置是“能级”可以通过下面的打印观察出来。 ct 0print( 数值, ran, dom 4_dom )print( ----------------------- )for i in range(1,2000): if i%4 0: v what_is_the4(n) v v[0] str(v[1]) w abstr(i)[0] w what_is_the4(w) w w[0] str(w[1]) print ( {0: 5}{1: 5s}{2: 5s} .format(i,v,w)) ct 1 if ct% 16 0:ct 0;print( ---------------------** ,w) elif ct%4 0:print( ----------------------- ,w) 在研究那些转换规律时 有些带来数值的爬升 有些则下降 但是能否一直爬升或者一直下降 在同态爬升中只有c- c 的转换出现 很明显 一个有限的能级值i, 它的若要保持后继的i j奇性不变 只能 i 1 2^n 经过n次转转后 还是要改变奇偶性 也就是说 一直c态爬升是不可能的。c态最终变成a态。a态又经过b态或者d态下降变回a或c态 但也有可能变成d态后就一直下降到a0 1了。详细讨论这些路径应当很有趣 比如 a- b- a- b- a 最初a 和最终a的升降。下面考察一下collatz(27) print()def collatz_see_me(n): if n 0: print( 初始值 ,n, 不符合条件 );return while n ! 1: if n%2 0: # (1) v what_is_the4(n); v v[0] str(v[1]) print(n,v, ↓ ) n n//2 elif n%2 1:# (2) v what_is_the4(n);v v[0] str(v[1]) print(n,v, \\n------ ) n n*3 1 print(n)#collatz_see_me(27) collatz变换 将对态和能级进行转变。collatz(27)的峰值达到 9232 d2308 d态的2308级假如态数目 尺度 变大的话 那么一个整数的能级将变小 比如把它放到128态数上面观察 峰值是9232 16s:72 第16态的72级 def states(n,mod 128,s s ):# n是任意正整数 mod为尺度 s为态的标记符号 nevel n//mod st n%mod return str(st) s : str(nevel)def collatz_see(n): if n 0: print( 初始值 ,n, 不符合条件 );return while n ! 1: if n%2 0: # (1) v states(n) print(n,v, ↓ ) n n//2 elif n%2 1:# (2) v states(n) print(n,v, \\n------ ) n n*3 1 print(n)#collatz_see(27) 可以看出 假如态数数目很大 比如16384 2^14 9232 那么collatz(27)的整个过程将会在0级里面打转。特定态数目下的collatz变换的规律 是和能级之间的转换 跳跃 密切相关的 但我们也看到 态数目很大的时候 一定范围内的整数 没有能级之间的跳跃 只在0级中进行态的转变。这说明了什么 把地图放大看 #十进制 可以说是10态数 到底有什么规律 我说不出来。但是下面打印出来的右边的能级是有一些规律的 就是间隔着插入10个0 10个1 10个2...for n in range(500): if n%2 0: v states(n,mod 10) w states(n//2,mod 10) print(n,v, ,w) elif n%2 1: v states(n,mod 10) w states((n*3 1)//2,mod 10) print(n,v, ,w) 因为colatz涉及到(同余)和分形 下面以同样的方式来构造一个类似的函数。可以看到其中有一个大的(循环)节点 还有类似归吸引力的0 1 2这三个循环节点。 def run(w, stop_counter, blackhole): #为了防止陷入死循环 设置了stop_counter t stop_counter c []; ori w # 保留原始值 print(ori) dangerous blackhole | {0,1,2,3} while w not in dangerous: # 类似于 collatz 不等于 1 的条件 if w%3 0: # 类似于 collatz 偶数 w w//3 if w not in c: # 这个判断是原来不知道有黑洞的情况下 用来探测黑洞的 c [w]; else: #print(c) p c.index(w) return c[p:] else: r w%3 w 5*w-2*r # 类似于 collatz 奇数*3 1 的条件 经过这样处理 w%3 0 t- 1 if t 0: return 2, ori,len(c) # 原始值可能 导向黑洞 这时采取退出机制 return 1q [227, 377, 627, 209, 347, ## 这是默默无闻的“弥伽”黑洞 577, 961, 1601, 2667, 889, 1481, 2467, 4111, 6851, 11417, 19027, 31711, 52851, 17617, 29361, 9787, 16311, 5437, 9061, 15101, 25167, 8389, 13981, 23301, 7767, 2589, 863, 1437, 479, 797, 1327, 2211, 737, 1227, 409, 681]blackhole set(q)for i in range(1,20000): v run(i, 30*i ,blackhole) if v is not 1: # 在充分的测试下 stop_counter 30*i 全跑完 可能遇到 危险区域 print(i,v); break 假如你的cpu很弱 那么 这个程序会有些卡顿,因此这也是一个测试cpu的程序