Hofstadter G序列的树形结构图和角谷x+1树的结构完全相同,每一层的个数都为斐波那契数列,上一层生成下一层的规律都为01序列后面加0或加1,两个1不能相临,即01序列结尾为0可以加1或0,01序列结尾为1只能加0。两个树形结构相同,但是他们对应整数的方式完全不同,生成的来源也完全不同。这其中可以包含一些原因,可以启发探索3x+1的性质。
G序列与x+1序列的树图结构完全相同,我们统计他们表示数的一些对应规律,探索两者对应的一些特征。
Hofstadter G序列: G(n) = n – G(G(n – 1)) ,其中 G(1) = 1 。这个序列的前 30 项如下:G(1) = 1 。这个序列的前 30 项如下:
如果把每个标号为 n 的结点都连接到标号为 G(n) 的结点下方,这样的话你将会得到一棵树。
从第二行开始算起,各行的结点个数依次为 1, 1, 2, 3, 5, 8, 13, … 正好是著名的 Fibonacci 数列(每个数都是前两个数之和)。即当 n ≥ 2 时,这棵树的第 n 行的结点总个数为 Fibonacci 数 Fn-1 。另外,这棵树的前 n 行的结点总数(也就是第 n 行最右边那个结点的编号)正好等于 Fn+1 ,也是一个个的 Fibonacci 数。可以看到 Hofstadter序列生成的树图和x+1的树图完全相同。