iを紡ぐ

巨大数入門　〜グラハム数を理解する〜

執筆者： kou
最終更新日：22.3.19

皆さんは、グラハム数という数を知っているだろうか。数学や雑学が好きな人なら知っているかもしれないが、グラハム数は数学の問題の証明に使われたことがある数の中で最大の数である。だが、グラハム数を知っている人でも、それがどのような数なのかを知っている人は少ないだろう。この記事では、巨大数に関する議論の最初のほんの一部である、グラハム数について理解できるくらいの内容を取り上げる。

指数タワー

数学における巨大数の分野では我々にとっては途方もないような数が研究されている。もちろん、それらの中にも比較的小さい巨大数から、巨大数の中でも上位に位置するような極めて大きなものまでさまざまな大きさの数がある。そして、巨大数について知るのであれば、やはり比較的小さめの巨大数から始め、そのあとにより大きな巨大数について考えた方がわかりやすいだろう。

ということで、ここでは巨大数の中でも最弱の指数タワーについて説明する。名前からなんとなく意味を理解できた人も多いだろうが、指数タワーはその名の通り指数を何重にも重ねた数である。例えば、下のような数が挙げられる。

$$\huge 9^{9^9} $$

もちろん、タワーの高さは指定されていないから、 $ 9 $ を $ 100 $ 個でも $ 200 $ 個でも、 $ 9^{9^9} $ 個でも肩に乗せてよいのである。

ここで、この表記方法で最も効率的に大きな数を表す方法は何だろうか。巨大数において、この問題は非常に重要な意味を持つ。数を大きくするのに一番重要な部分だけを考えることで議論を単純化できるからだ。

まず、次のような指数タワーを考える。

$$\large 3^3 $$

タワーというか、二段なのでタワーとは呼べないような数だが、これを実際に計算すると $ 27 $ となる。さて、この数に何らかの変化を加えて数を大きくしたい。どうすれば最も効率的に数を大きくできるだろうか。まずは次の二つについて考えてほしい。

$$\large 3^5\quad\quad5^3 $$

元の $ 3^3 $ のうち、片方の数を $ 5 $ に変えたものだ。これを計算すると、左が $ 243 $ で、右が $ 125 $ である。どちらも元の数よりは大きくなっているのだが、上げ幅を見てみると左の方が大きくなっている。このことから、 $ a^b $ という数について、これを大きくしたいならば、 $ a $ よりも $ b $ を大きくすることの方が重要であると考えられる。また、同じように考えれば、どんな高さのタワーでも、数字を大きくするならタワーの高い部分の数字を大きくした方が効率的に数を大きくすることができるとわかるだろう。しかし、これ以外にも数字を大きくする方法がある。それは、肩にさらに数字を増やすというものである。例えば、下のような数を考える。

$$\large 3^{3^2} $$

これを計算すると $ 3^9=19683$ となる。先ほどの左の数字は $ 243 $ なので、それと比べるとはるかに大きくなったのがわかるだろう。もちろん、数字を大きくする際、 $ 3^5 $ ではなく、 $ 3^{100} $ にすれば $ 19683 $ なんて容易に超えることができる。しかし、そうするくらいだったら $ 3^{3^{100}} $ にすることでさらに大きい数を作ることができる。このことから、肩に数字を増やすことは元の数を変化させるよりも効率的に数を大きくできるといえるだろう。

これまでのことをまとめると、指数タワーにおいては、数を大きくする方法の優劣は以下のように言える。

タワーを高くする ≫ タワーの上の方の数を大きくする ＞ タワーの下の方の数を大きくする

テトレーション

さて、巨大数界最弱の指数タワーをマスターしたところで、次は巨大数界で2番目に弱いテトレーションについて考えていこう。先の議論で、指数タワーを使って数を効率的に大きくするためにはタワーを高くすることが最もよいとわかった。ということは、タワーを効率的に高くすることができればさらに大きい数を作ることができるのではないか、という考えで作られたのがテトレーションである。テトレーションの定義は以下のようなものである。

テトレーション

$ a $ テトレーション $ b $ とは、 $ a $ を $ b $ 個使ってタワーを作ったもの。 $\huge\boldsymbol{ {}^b a }$ と表す。

定義は単純だが、念のため実際に数を代入して計算をしてみよう。 $ 3 $ テトレーション $ 3 $ を計算してみる。

\begin{align} {}^3 3 &=3^{3^3} \\ &=3^{27} \\ &=7625597484987 \end{align}

$ 3 $ という数字を2個しか使っていないのにものすごく大きい数になった。

テトレーションではどうすれば効率的に数を大きくできるだろうか。なんとなく察している人もいるだろうが、テトレーションであっても指数タワーの時と考え方は同じである。タワーを高くすることが数字を大きくする最も効率が良い方法であり、もともとの数字を大きくするならできるだけ高いところにある数字を大きくする方がよい。

ハイパー演算

次は巨大数界で3番目に弱い表記方法について･･･とはいかない。これまでの考えを一般化してみよう。数学における一般化の重要性は言うまでもないが、実はこれまでの議論を一般化したハイパー演算というものがある。

これまでの流れをおさらいすると、ある数を何回掛け算したかを累乗で表し、ある数を何回累乗したかをテトレーションで表した。ということは、テトレーションを何回重ね合わせたかを表す演算があってもいいはずである。もちろんそれは存在し、ペンテーションと呼ばれる。ということは、ペンテーションを何回重ね合わせたかを表す演算があってもいいはずである。それも存在し、ヘキセーションと呼ばれる。ここから先は言うまでもないだろう。

このように、ある演算を複数繰り返すことを一般化したもの、言い換えると、和・積・累乗を一般化させたものがハイパー演算である。ハイパー演算は次のような階層になっている。

\begin{aligned} a \; \underbrace{ +1+1+1+\cdots+1 }_{b\text{個}} &= \large\boldsymbol{ a+b } \\ \underbrace{ a+a+a+a+\cdots+a }_{b\text{個}} &= \large\boldsymbol{ a \times b } \\ \underbrace{ a \times a \times a \times a \times \cdots \times a }_{b\text{個}} &= \large\boldsymbol{ a^b } \\ \underbrace{ {\huge a}^{{\huge a}^{{\huge a}^{\cdot^{\cdot^{\cdot^{\huge a}}}}}}}_{b\text{個}} &= \large\boldsymbol{ {}^b a } \end{aligned}
監修者注）お気づきだろうが、ふだん私たちの使っている「 $ a+b $ 」「 $ a\times b $ 」「 $ a^b $ 」という演算は、前に定義した演算を複数回行うことを表す、ハイパー演算の一種だったのである。

テトレーションの「テトラ」は「4」の意味だが、上のように考えると確かにテトレーションが4番目のハイパー演算であることが見てとれる。

クヌースの矢印表記

さて、グラハム数はまだかという声もちらほらと聞こえてきそうになってきたが、ここで紹介するクヌースの矢印表記こそが、グラハム数を理解するのに必要な演算である。ここを理解すればグラハム数は目前なので頑張ってほしい。

定義

クヌースの矢印表記はその名の通り矢印 $ \uparrow $ を使って表される演算である。この演算の定義は以下のようなものである。

\begin{aligned} \large\boldsymbol{a \uparrow b} &= \large{a^b}\\\\ \large\boldsymbol{a \uparrow\uparrow b} &= \underbrace{ a \uparrow a \uparrow \cdots \uparrow a \uparrow a }_{b\text{個}} \\ &= \underbrace{ {\large a}^{{\large a}^{{\large a}^{\cdot^{\cdot^{\cdot^{\large a}}}}}} }_{b\text{個}} \quad = \large{{}^b a} \\\\ \large\boldsymbol{a \uparrow\uparrow\uparrow b} &= \underbrace{ a \uparrow\uparrow a \uparrow\uparrow \cdots \uparrow\uparrow a \uparrow\uparrow a } _{b\text{個}} \\\\ \large\vdots\\\\ \large\boldsymbol{ a \underbrace{ \uparrow\uparrow\cdots\uparrow }_{n\text{個}} b } &= \underbrace{ a \underbrace{ \uparrow\cdots\uparrow }_{n-1\text{個}} a \underbrace{ \uparrow\cdots\uparrow }_{n-1\text{個}} a \underbrace{ \uparrow\cdots\uparrow }_{n-1\text{個}} \cdots \underbrace{ \uparrow\cdots\uparrow }_{n-1\text{個}} a }_{b\text{個}} \\\\ \end{aligned}

演算 $ \uparrow $ は右結合である。右側から計算する。たとえば

$$ a \uparrow a \uparrow a = a \uparrow \left( a \uparrow a \right) $$

であり、

$$ a \uparrow a \uparrow a \uparrow a = a \uparrow \left( a \uparrow \left( a \uparrow a \right)\right) $$

である。

いちいち、 $ a \underbrace{ \uparrow\uparrow\cdots\uparrow }_{n\text{個}} b $ と書くのは煩雑なので、 $ \uparrow $ を $ n $ 個並べたものを $ a \uparrow^n b $ で表す。

$$ a \uparrow^n b = a \underbrace{ \uparrow\uparrow\cdots\uparrow }_{n\text{個}} b $$

たとえば $ \uparrow\uparrow $ は $ \uparrow^2 $、 $ \uparrow\uparrow\uparrow $ は $ \uparrow^3 $ である。

この記法によると、 $ a \uparrow^n b $ は、

$$ a \uparrow^n b = \underbrace{ a \uparrow^{n-1} a \uparrow^{n-1} a \uparrow^{n-1} \cdots \uparrow^{n-1} a \uparrow^{n-1} a }_{b\text{個}} $$

と定義できる。

再帰的定義。あるいは漸化式に似たものを感じる

練習

さて、今回はやや定義が複雑なので実際にいくつか計算してみよう。

\begin{aligned} 3\uparrow3 &=3^3\\ &=27\\\\ 3\uparrow\uparrow3 &={}^3 3\\ &=7625597484987\\\\ 3\uparrow\uparrow\uparrow3 &=3\uparrow\uparrow3\uparrow\uparrow3\\ &=3\uparrow\uparrow7625597484987\\ &={}^{7625597484987}3 \end{aligned}

となり、 $ 3 $ が $ 7625597484987 $ 段ある指数タワーとなる。

ここまでくればグラハム数を理解するのにあと一歩のところであるが、ここで恒例の、どうすれば効率的に数を大きくできるか問題に挑戦しよう。選択肢は3つ。

である。とはいえ、上の計算を見るとどれが一番よいかはなんとなくわかるだろう。正解は、

矢印の数を増やす ≫ 矢印の後の数字を増やす ＞ 矢印の前の数字を増やす

である。

関数の埋め込み

この部分は合成関数について知っている人は飛ばして読んでいただいて構わない。ここでは、関数を別の関数に埋め込むということについて説明する。例えば、次のような二つの関数があったとする。

\begin{align} f(x) &= x+1\\ g(x) &= x^2 \end{align}

ここで、 $ f\left(g(x)\right) $ という関数を考える。これは、関数 $ f(\;) $ の変数に $ g(x) $ という別の関数を代入するという意味である。

\begin{align} f(g(x)) &= g(x) + 1 \\ &= x^2 + 1. \end{align}

同様にして、 $ g(f(x)) $ について考えると、

\begin{align} g(f(x)) &= \left\{f(x) \right\} ^2 \\ &= (x+1)^2 \end{align}
となる。

埋め込む関数が自分と同じ関数でも構わない。例えば、

\begin{align} f(f(x)) &= f(x)+1 \\ &= (x+1)+1 \\ &= x+2 \\\\ g(g(x)) &= \left\{g(x) \right\} ^2 \\ &= (x^2)^2\\ &= x^4 \end{align}
である。

埋め込みは複数回行える。たとえば、

\begin{align} f(f(f(x))) &= f(f(x))+1 \\ &= (f(x)+1)+1 \\ &= ((x+1)+1)+1 \\ &= x+3 \end{align}

ここで、 $ f(f(x)) $ を

$$ \large f^2(x) $$
で表す。同じように、 $ f(f(f(x))) $ を $ f^3(x) $ で表す。

$$ \large f^n(x)= \underbrace{ f(f(\cdots f(f(x))\cdots)) }_{n\text{個}} $$

グラハム数

ついにグラハム数を紹介できる時がきた。

グラハム数とは、グラハム問題という問題を成立させる解の上限として発表された数であり、数学の証明において用いられた数の中で最大の数である。それは、以下のような数である。

$\boldsymbol{G(n)=3\uparrow^n3 }$ として、 $\boldsymbol{ G^{64}(4) }. $

これで理解できたら素晴らしいが、なんとなくぴんと来ない感じがする。そこで、以下のように考えてみよう。

\begin{align} G(4) &= 3\uparrow\uparrow\uparrow\uparrow3 \\\\ G^2(4) &= 3\uparrow^{G(4)}3\\ &= 3\; \underbrace{ \uparrow\uparrow\cdots\uparrow\uparrow }_{ G(4)=3\uparrow\uparrow\uparrow\uparrow3 \text{個} } \;3 \\\\ G^2(4) &= 3\; \underbrace{ \uparrow\uparrow\cdots\cdots\uparrow\uparrow }_{ G(4) \text{個} } \;3 \\\\ \cdots&\cdots\cdots\cdots\cdots\cdots\\\\ G^{k+1}(4) &= 3\; \underbrace{ \uparrow\uparrow\cdots\cdots\cdots\uparrow\uparrow }_{ G^k(4) \text{個} } \;3 \\\\ \cdots&\cdots\cdots\cdots\cdots\cdots\\\\ G^{64}(4) &= 3\; \underbrace{ \uparrow\uparrow\cdots\cdots\cdots\cdots\uparrow\uparrow }_{ G^{63}(4) \text{個} } \;3 \\ &=\textbf{グラハム数} \end{align}

こう考えると途方もない数である。

ということで、今回の記事でやりたいことは大体終わった。いかにグラハム数が大きい数かわかってもらえたことだろう。少なくとも指数表記やテトレーションなんかでは宇宙の全てを使っても表現できないほどの大きさである。

その先へ

さて、グラハム数についての説明が終わったが、グラハム数は巨大数の世界ではどのくらいの大きさなのかについて話しておこう。実は、グラハム数はあんなにも大きい数なのに巨大数の世界では最弱クラスの数なのだ。グラハム数の定義を見直すと、一つの関数を64回も関数に埋め込んでいる。しかし、巨大数の世界では、そんなことをしなくても容易にグラハム数を超える数がたくさん存在するのだ。例えば、コンウェイのチェーン表記という表記方法を使えば、

$$ 3\rightarrow3\rightarrow65\rightarrow2 $$

という数はグラハム数よりも大きくなる。また、多変数アッカーマン関数という関数を使えば、$ A(1,1,65) $ という数はグラハム数よりも大きくなる。さらに言えば、 $ \text{TREE} $ 数列という数列では、 $ \text{TREE}(3) $ の時点でグラハム数よりもはるかに大きくなる。関数の埋め込みも使わず、こんなにコンパクトに超えられてしまうのだ。

とはいえ、大きいことには変わりない。例えば、グラハム数の桁数について考えてみよう。いやいや、あんな複雑な数の桁数なんて計算できるのかと思った人もいるかもしれない。しかし、実際のところ計算なんてしなくてもよいのである。ある数 $ A $ の桁数を知りたければ、その常用対数 $ \log_{10} A $ を考えればよい。ところで、グラハム数ほどの数になると、なんと

$$ \boldsymbol{ \textbf{グラハム数} \risingdotseq \log_{10} \textbf{グラハム数} } $$

という驚くべき近似式が成立する。桁数はもはや自分自身の数の大きさとさして変わらないのだ。累乗はハイパー演算の3番目であるが、グラハム数の用いる演算はハイパー演算の $ G^{63}(4)+2 $ 番目である。全く格が違う。

おまけ

こんな記事を最後まで読んでくれたあなたのために、一つ問題を用意した。すでに習った数学とこの記事の情報だけで解くことができるから、時間があったら挑戦してみてほしい。ネットにはこの問題の答えがあるので、どうしてもわからなかったら見てみると良い。

問題 グラハム数を十進数で表すとその一桁目の数字はいくつ？