趣题:用树来表示数(已更新)

你能找出规律吗?明天晚上公布问题答案,并探讨一些延伸话题。


Update: 抱歉昨晚有些突发情况,没能更新。

这个问题来自于 这里 。没错,图中的规律就是:每棵树代表一个质数,一个森林(若干个树放一块儿)就表示这些质数的乘积;如果一个森林表示的是 n ,在这个森林下方添加一个公共根,就构成了新的质数——第 n 个质数。例如, 69 就等于 3 乘以 23 ,它们分别是第 2 个质数和第 3×3 个质数。 131 这个例子更能说明问题,因为它就是第 32 个质数。

这个东西牛就牛在,它建立了一个自然数到森林的一一对应关系(从而也就建立了自然数到有根树的一一对应关系,因为我们可以用添加超级根的方法把森林都视作树)。这种为有根树编号的方法叫做 Matula-Goebel 编号法,参见数列 A127301

注意到质因数分解在构造一一对应关系中的妙用。正是因为有唯一分解定理,数的表示方法才是唯一的。于是乎,图论和数论巧妙地结合在了一起,实在令人拍案叫绝。

发表评论

9  ×  1  =