Skip to main content

大数 & 无穷

· 7 min read

一些很大很大的数……以及从有限走向无穷。

参考资料​

简介​

我们每天都在用数字，平时用「天文数字」形容极大的数字，会用科学计数法表示。但再往后还有很多更大的数字，「大数」是指远超出了日常生活使用范围的数字。

超运算​

超运算（Hyperoperation）是把「重复前一级运算」这一过程不断递归推广所得到的一族运算，从加法、乘法、幂运算一直向上延伸。

我们将 后继运算 定义为零级运算（超-0 运算）：

a[0]b=H0(a,b)=b+1a[0]b=H_0(a,b)=b+1

若要把后继运算重复 bb 次，我们引入 加法运算，即一级运算（超-1 运算）：

a[1]b=H1(a,b)=a+b=a+1+1+⋯+1⏟ba[1]b=H_1(a,b)=a+b=a+\underbrace{1+1+\dots+1}_b

若要把 aa 连续相加 bb 次，我们引入 乘法运算，即二级运算（超-2 运算）：

a[2]b=H2(a,b)=a×b=a+a+⋯+a⏟ba[2]b=H_2(a,b)=a\times b=\underbrace{a+a+\dots+a}_b

若要把 aa 连续相乘 bb 次，我们引入 幂运算，即三级运算（超-3 运算）：

a[3]b=H3(a,b)=ab=a×a×⋯×a⏟ba[3]b=H_3(a,b)=a^b=\underbrace{a\times a\times\dots\times a}_b

不难发现，每一级运算都是对前一级运算的重复，而 nn 级运算记作 a[n]ba[n]b 或 Hn(a,b)H_n(a,b)：

Hn(a,b)=a[n]b={b+1n=0an≥1∧b=1Hn−1(a,Hn(a,b−1))otherwiseH_n(a,b)=a[n]b= \begin{cases} b+1 & n=0 \\ a & n\ge 1\land b=1 \\ H_{n-1}(a,H_n(a,b-1)) & \text{otherwise} \end{cases}

继续推广，四级运算（超-4 运算）定义为 重幂运算（Tetration），也称为 迭代幂次：

a[4]b=H4(a,b)=ba=aa⋅⋅⋅a⏟ba[4]b=H_4(a,b)={}^b a=\underbrace{a^{a^{\cdot^{\cdot^{\cdot^a}}}}}_b

五级运算（超-5 运算）其实也有特殊记号，但并不常用：

a[5]b=H5(a,b)=ba=a⋅⋅⋅aa⏟ba[5]b=H_5(a,b)={}_b a=\underbrace{{}^{{}^{{}^{{}^{{}^a\cdot}\cdot}\cdot}a}a}_b

再往后就要用 a[n]ba[n]b 或 Hn(a,b)H_n(a,b) 表示，并根据递推公式计算。

大数记号​

高德纳箭号表示法​

高德纳箭号表示法（Knuth's Up-arrow Notation）是一种大数的表示方法，其定义为：

a↑nb=a[n+2]b=Hn+2(a,b)a\uparrow^n b=a[n+2]b=H_{n+2}(a,b)

例如：

a↑b=aba\uparrow b=a^b a↑↑b=aa⋅⋅⋅a⏟ba\uparrow\uparrow b=\underbrace{a^{a^{\cdot^{\cdot^{\cdot^a}}}}}_b

约定高德纳箭号符合右结合律，可以得到递推关系：

a↑nb=a↑↑⋯↑⏟nb=a↑n−1a↑n−1⋯↑n−1a⏟ba\uparrow^n b=a\underbrace{\uparrow\uparrow\dots\uparrow}_n b=\underbrace{a\uparrow^{n-1}a\uparrow^{n-1}\dots\uparrow^{n-1}a}_b

例如：

3↑3=33=273\uparrow 3=3^3=27 3↑↑3=3↑3↑3=3↑27=333=327≈7.63×10123\uparrow\uparrow 3=3\uparrow 3\uparrow 3=3\uparrow 27=3^{3^3}=3^{27}\approx 7.63\times 10^{12} 3↑↑↑3=3↑↑3↑↑3=3↑↑327=33⋅⋅⋅3⏟3273\uparrow\uparrow\uparrow 3=3\uparrow\uparrow 3\uparrow\uparrow 3=3\uparrow\uparrow 3^{27}=\underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{3^{27}} 3↑↑↑↑3=3↑↑↑3↑↑↑3=3↑↑↑33⋅⋅⋅3⏟327=33⋅⋅⋅3⏟33⋅⋅⋅3⏟⋮⏟3}33⋅⋅⋅3⏟33⋅⋅⋅3⏟⋮⏟3}33\uparrow\uparrow\uparrow\uparrow 3=3\uparrow\uparrow\uparrow 3\uparrow\uparrow\uparrow 3=3\uparrow\uparrow\uparrow\underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{3^{27}}=\left.\left.\underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{\underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{\underbrace{\vdots}_3}}\right\}\underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{\underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{\underbrace{\vdots}_3}}\right\}3

康威链式箭号表示法​

康威链式箭号表示法（Conway Chained Arrow Notation）是由约翰 · 何顿 · 康威（John Horton Conway）发明的一种大数的表示方法。

其形式是一串用箭头（→\to）连接的数字，定义如下：

  1. aa 表示正整数 aa；
  2. a→ba\to b 表示 aba^b；
  3. a→b→1a\to b\to 1 等价于 a→ba\to b；
  4. a→b→(c+1)a\to b\to(c+1) 等价于 a→(a→(…(a→(a)→c)… )→c)→c⏟b\underbrace{a\to(a\to(\dots(a\to(a)\to c)\dots)\to c)\to c}_b。

三项链的康威链式箭号表示法和其他记号的关系：

a→b→c=Hc+2(a,b)=a↑cba\to b\to c=H_{c+2}(a,b)=a\uparrow^c b

阿克曼函数​

阿克曼函数（Ackermann Function）是由威廉 · 阿克曼（Wilhelm Ackermann）提出的一个非原始递归函数。

A(m,n)={n+1m=0A(m−1,1)m>0∧n=0A(m−1,A(m,n−1))m>0∧n>0A(m,n)= \begin{cases} n+1 & m=0 \\ A(m-1,1) & m>0\land n=0 \\ A(m-1,A(m,n-1)) & m>0\land n>0 \end{cases}

对于接触过算法竞赛的读者，应该并不陌生。

int A(int m,int n)
{
	if(m==0)return n+1;
	if(n==0)return A(m-1,1);
	return A(m-1,A(m,n-1));
}

阿克曼函数和其他记号的关系：

A(m,n)=Hm(2,n+3)−3=2↑m−2(n+3)−3A(m,n)=H_{m}(2,n+3)-3=2\uparrow^{m-2}(n+3)-3

我们通常用一元函数 A(n)A(n) 代替 A(n,n)A(n,n)，还可以通过嵌套函数快速提高增长速度：

A3(n)=A(A(A(n)))A^3(n)=A(A(A(n)))

常见大数​

葛立恒数​

葛立恒数曾是以下问题中 nn 极其宽松的上界，但现在已经压缩到 2↑↑↑52\uparrow\uparrow\uparrow 5 了。

考虑一个 nn 维超立方体，在连接所有顶点后，将形成一个 2n2^n 个顶点的完全图。将每条边红蓝染色，求最小的 nn 使得所有染色方案中，都必定存在一个四点共面且六边同色的单色完全子图。

其定义为：

g1=3↑↑↑↑3g_1=3\uparrow\uparrow\uparrow\uparrow 3 gn=3↑gn−13g_n=3\uparrow^{g_{n-1}}3 G=g64=3↑↑⋯↑⏟33↑↑⋯↑⏟3⋮3↑↑⋯↑⏟33↑↑↑↑3}64G=g_{64}= \left.\begin{matrix} 3\underbrace{\uparrow\uparrow\dots\uparrow}3 \\ 3\underbrace{\uparrow\uparrow\dots\uparrow}3 \\ \vdots \\ 3\underbrace{\uparrow\uparrow\dots\uparrow}3 \\ 3\uparrow\uparrow\uparrow\uparrow 3 \end{matrix}\right\}64

葛立恒数的大致范围：

G≈A64(4)G\approx A^{64}(4) 3→3→64→2<G<3→3→65→23\to 3\to 64\to 2<G<3\to 3\to 65\to 2

TREE 函数​

TREE 函数（TREE Function）是由克鲁斯卡尔树定理引出的数列，定义为满足以下条件的最大序列长度：

用编号 { 1,…,n }\set{1,\dots,n} 染色的有根树，第 ii 棵树最多有 ii 个节点，并且使得没有任何较早的树能同胚嵌入到第 ii 棵树中。

其中 TREE⁡(1)=1,TREE⁡(2)=3\operatorname{TREE}(1)=1,\operatorname{TREE}(2)=3。这个函数一定是有限的，但从 TREE⁡(3)\operatorname{TREE}(3) 开始就变得极其巨大。

TREE⁡(3)\operatorname{TREE}(3) 的大致范围：

TREE⁡(3)>AA(187196)(1)\operatorname{TREE}(3)>A^{A(187196)}(1)

无穷​

推荐阅读乔治 · 伽莫夫的《从一到无穷大》，也可以观看李永乐老师的讲解课程 从一到无穷大。