简介

问题陈述(继承n进制表示 古德斯坦序列)

简介

古德斯坦定理是由鲁宾·古德斯坦提出的一条关于自然数的命题，即所有古德斯坦序列最终均结束于0。古德斯坦本人用集合论方法证明了这个定理，科比和帕里斯则在1982年证明了该命题在皮亚诺公理系统内是不可证的。

问题陈述

继承n进制表示

古德斯坦序列是由一种称为“继承n进制表示”的概念定义的。这种表示十分类似于通常的n进制表示，但通常的n进制表示对古德斯坦定理是不够的。

普通的n进制表示（n为大于1的自然数）中，任意的自然数m被写作n的幂的倍数的和：

m=ak*n^k+a(k-1)*n^(k-1)+...+a0，

其中每个系数ai满足0≤ai<n，且ak≠0。例如，在二进制下，

35=32+2+1=2^5+2^1+2^0。

所以35的2进制表示就是2^5+2^1+2^0。（可写作二进制的100011。）同样地，可将100用3进制表示：

100=81+18+1=3^4+2*3^2+1。

注意指数本身并不写作n进制。例如，上面的表示就包含2^5和3^4。

要把通常的n进制表示转换为继承n进制表示，首先把所有的指数改写为n进制，然后改写指数的指数，以此类推，直到每一个在这个表示中出现的数字都不比n大。

例如，35的继承2进制表示：

35=2^2^2+1+2+1；

100的继承3进制表示：

100=3^(3+1)+2*3^1+1。

古德斯坦序列

一个自然数m的古德斯坦序列G(m)是一个自然数序列。这个序列的第一个元素就是m本身。要得到第二个元素，首先把m写作继承2进制表示，把其中所有的2改为3，然后再减1；这就是G(m)的第二个元素。要得到第三个元素，把第二个元素写成继承3进制表示，把所有3改为4，再减1。一直继续到结果为0，此时这个序列终止。

尽管古德斯坦序列常常增长得快得惊人，古德斯坦定理指出每个古德斯坦序列最终终止于0。