8.2　考拉兹猜想的树形图

图8-2显示的是我们在讨论考拉兹猜想的书籍或论文中常常看到的树形图。每个数字在分支中以从上往下的方向显示考拉兹序列中的数字，例如之前列举的数字13，顺着13往下便能找到根据考拉兹规则计算出的那一系列数字。迄今为止调查到的所有数字都会到达4、2，最后再到1，因此所有数字都是起源于同一树中的分支。美国阿肯色大学的埃德蒙·哈里斯（Edmund Harriss）教授又提出了另外一种图形化的方法，他在标准图的基础上新添了一条关于分支方向的规则，用来反映一个数字是由两种算法中的哪一种运算而生成，即：无论你是树枝中的哪个数字，如果在你上面的数字是你的2倍，则上端分支会以固定角度向顺时针方向转动；如果不是2倍，则以固定角度向逆时针方向转动。这样得到如图8-3所示的形状。如果把数字去掉，并对线条着色，我们就可以得到一个像是正在野蛮生长的水藻或是正在绽放的礼炮的动画，它的实现也不太复杂，我们来动手实现一下。

图8-2　考拉兹树形图

图8-3　第二种考拉兹树形图

要实现图8-3中第二种考拉兹树形图首先要找到树形关系图，我们在玩游戏时是正推，比如3→10→5→16→8→4→2→1，但是现在需要倒推，也就是说，我们要找什么数会走到1，很显然只有2，什么数能走到2，只有4，如此往上逆推，当走到16时，情况发生了变化，32→16，5→16，也就是说16有{32，5}两个父节点，然后，我们要继续为32和5找父节点。很明显，一个永远存在的父节点就是自身的2倍；另一个则可以通过化简正向推演的公式求出，当前数是奇数时，我们就乘3加1，写成数学表达式就是

因为

k=3n+1

所以

n=（k-1）/3

执行这个运算的前提是k-1能被3整除，另外还要保证求出来的n一定要是奇数，否则根本就不是执行乘3加1这个操作。怎么保证这两个条件呢，我们把n改写成2m+1，代入到k=3n+1，可以得到

因为

k=3（2m+1）+1=6m+4

所以

（k-4）mod 6=0

也就是说k-4要能被6整除，才需要计算n=（k-1）/3整个操作。

通过几次简单手算以后，很快发现，每往上推演一层，就会有多个节点，每个节点又会延伸出最多两个父节点（有些只有一个父节点，比如6），整个结构就是一个典型的树状结构，这种数据结构怎么存储比较方便呢？我们下面介绍Python的另一种数据结构——字典。