Goodstein函数

古德斯坦函数(Goodstein Function)是由鲁宾•古德斯坦(Reuben Goodstein)构造出的快速增长的函数。

定义

首先需要定义数m的以n为底的遗传记法：

假设我们将一个非负整数m表示为n的幂次之和，然后将这些幂指数本身也表示为类似的幂次和，不断重复这一过程，直到所有的最高次指数都小于n。例如，我们可以将100写作 $2^{6} + 2^{5} + 2^{2}$ 进一步可以写为 $2^{2^{2} + 2} + 2^{2^{2} + 1} + 2^{2}$ 。这种表示方式称为m的以n为底的遗传记法。

Goodstein定义了一个数列 $G_{k} (n)$ ：

对任意自然数n，都有 $G_{0} (n) = n$

对任意自然数n,k，都有 $G_{k + 1} (n)$ 是把 $G_{k} (n)$ 写成以k+2为底的遗传记法，随后把里面所有的k+2改成k+3，最后再把整个数减一所得到的数。

我们拿100作为例子：

$G_{0} (100) = 100 = 2^{2^{2} + 2} + 2^{2^{2} + 1} + 2^{2}$

$G_{1} (100) = 3^{3^{3} + 3} + 3^{3^{3} + 1} + 3^{3} - 1 = 3^{3^{3} + 3} + 3^{3^{3} + 1} + 3^{2} \times 2 + 3 \times 2 + 2 = 228767924549636$

$G_{2} (100) = 4^{4^{4} + 4} + 4^{4^{4} + 1} + 4^{2} \times 2 + 4 \times 2 + 1 \approx 3.486030062 \times 1 0^{156}$

……

这种快速增长的序列称为 Goodstein 序列。令人惊讶的是，对于 n 的所有值， $G_{k} (n)$ 最终达到峰值、下降并返回零。这个事实被称为古德斯坦定理。更令人惊讶的是，可以证明古德斯坦定理无法用皮亚诺算术来证明。

我们定义古德斯坦函数 $G (x)$ 等于古德斯坦序列 $G_{k} (x) = 0$ 时k的值。

例子

我们以较小的x作为例子，来计算一下 $G (x)$ .为了更加清晰，我们不展示 $G_{k} (n)$ 的具体值，而是展示它的以k+2为底的遗传记法表示。读者可以自行计算取值。

x=1
k	$G_{k} (x)$ 以k+2为底的遗传记法表示
0	1
1	0

因此G(1)=1.

x=2
k	$G_{k} (x)$ 以k+2为底的遗传记法表示
0	2
1	2
2	1
3	0

因此G(2)=3.

x=3
k	$G_{k} (x)$ 以k+2为底的遗传记法表示
0	2+1
1	3
2	3
3	2
4	1
5	0

因此G(3)=5.

从G(4)开始，古德斯坦函数将开始“起飞”

x=4
k	$G_{k} (x)$ 以k+2为底的遗传记法表示
0	$2^{2}$
1	$3^{2} \times 2 + 3 \times 2 + 2$
2	$4^{2} \times 2 + 4 \times 2 + 1$
3	$5^{2} \times 2 + 5 \times 2$
4	$6^{2} \times 2 + 6 + 5$
9	$1 1^{2} \times 2 + 11$
10	$1 2^{2} \times 2 + 11$
21	$2 3^{2} \times 2$
22	$2 4^{2} + 24 \times 23 + 23$
45	$4 7^{2} + 47 \times 23$
46	$4 8^{2} + 48 \times 22 + 47$
93	$9 5^{2} + 95 \times 22$
189	$19 1^{2} + 191 \times 21$
381	$38 3^{2} + 383 \times 20$
402653181= $3 \times 2^{27} - 3$	$40265318 3^{2}$
402653182	$402653184 \times 402653183 + 402653183$
$3 \times 2^{402653210} - 3$	$3 \times 2^{402653210} - 1$
$3 \times 2^{402653210} - 2$	$3 \times 2^{402653210} - 1$
$3 \times 2^{402653211} - 3$	0

因此 $G (4) = 3 \times 2^{402653211} - 3$

这里它展示了很清晰的“下降”过程。

我们有G(12)大于葛立恒数这个结论。

与HH的关系

（待续）