グラハム数

他の用法については、グラハム数 (曖昧さ回避) をご覧ください。

グラハム数 (Graham's number) は、Ronald Grahamが定義した有名な巨大数である。

矢印表記を使って、このように定義出来る。

\begin{eqnarray*} G_0 &=& 4 \\ G_1 &=& 3 \uparrow\uparrow\uparrow\uparrow 3 \\ G_2 &=& 3 \underbrace{\uparrow\uparrow\cdots\uparrow\uparrow}_{G_1 \text{ 本の↑}} 3 \\ G_{k + 1} &=& 3 \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow\uparrow\uparrow}_{G_k \text{ 本の↑}} 3 \\ G_{64} &=& \text{グラハム数} \end{eqnarray*}

すなわち、\(G(n) = 3\uparrow^{n}3\) としたときの\(G^{64}(4)\)である。

表示をデスクトップ版に切り替えて数式を表示する。

グラハム数は数学の証明で使われた最大の数としてギネスブックにも登録されている。ちなみに、「数学的に意味のある」巨大数に関しては、TREE(3)、SCG(13)等、グラハム数より遥かに巨大なものが存在する。

巨大数漫画「寿司 虚空編」では、第1話でグラハム数の話からはじまり、読者を巨大数の世界へと引き込んでいる。

歴史

グラハム数は、次のラムゼー理論に関する未解決問題から生まれた。

Let N* be the smallest dimension n of a hypercube such that if the lines joining all pairs of corners are two-colored for any n ≥ N*, a complete graph K₄ of one color with coplanar vertices will be forced. Find N*.

グラハムは、この問題の答えが存在する事を証明する論文を発表し、その値の上限を \(F(n) = 2 \uparrow^{n} 3\) (矢印表記を使用)としたときの\(F^{7}(12)\)であるとした。Sbiis Saibian は、この数を"小グラハム数"と呼んだ。グラハム数は、この論文の前に未公表の論文に書かれていたことがあり、マーティン・ガードナーがサイエンティフィック・アメリカンにそのことを書いたことで有名になった。

ガードナーの記事には小さなミスがあり、\(3\uparrow\uparrow7625597484987=3\uparrow(7625597484987\uparrow7625597484987)\)であると書かれているが、実際には\(3(3\uparrow\uparrow7625597484987)\)である。

比較

\(G_0\)が3ではなくて4のため、巨大数論で使われる多くの関数で、グラハム数を正確かつ簡潔に表現することができないが、近似することはできる。チェーン表記では、\(3 → 3 → 64 → 2\)、配列表記では \(\lbrace 3,65,1,2\rbrace\) と近似でき、上限は \(\lbrace 3,66,1,2\rbrace\) である。多変数アッカーマン関数では、\(A(1,1,64)<G<A(1,1,65)\)である。

Tim Chow は、グラハム数がモーザー数よりもはるかに大きい事を証明した。 この証明は、スタインハウス・モーザー表記で(k + 2)角形の中の nは \(n\underbrace{\uparrow\uparrow\ldots\uparrow\uparrow}_{2k-1}n\) よりも小さいことを利用している。彼はこの証明を Susan Stepney に1998年7月7日に送った。 偶然にも、Stepney は Todd Cesere から同様の証明を数日後に受け取った。

グラハム数はビジービーバー関数の\(\Sigma(64)\)よりもずっと小さいことが証明されている。Googology WikiユーザーのWythagorasによると、Wythagorasは同じくGoogology WikiユーザーであるDeedlit11によるチューリングマシンを改良することで、\(\Sigma(18) > G\)を導くようなチューリングマシンを発見したと主張し、厳密な証明の代わりに証明のスケッチを公開した。

グラハム数は\(f_{\omega+1}(64)\)よりも小さいことがふぃっしゅによって証明されている。

最後の桁の計算

グラハム数は3の指数タワーなので、グラハム数の最後の桁は 一の位が収束することを利用して計算される。 グラハム数の最後の \(x\) 桁を \(N(x)\)としたときそれを求める簡単なアルゴリズムとして次のようなものがある:

• \(N(0) = 3\)
• \(N(x) = 3^{N(x-1)} \text{ mod } 10^x\)

例えば:

• \(N(1) = 3^{N(0)} \equiv 3^3 \equiv 27 \equiv 7 \pmod{10}\), よって最後のケタは7。
• \(N(2) = 3^{N(1)} \equiv 3^7 \equiv 2187 \equiv 87 \pmod{100}\), よって最後の2ケタは87。
• \(N(3) = 3^{N(2)} \equiv 3^{87} \equiv 323257909929174534292273980721360271853387 \equiv 387 \pmod{1000}\), よって最後の3ケタは387。
• 以下同様にして求められる。

左端の表記を計算した時の桁数は指数的に増えるので、この単純なやり方はあまり効率的ではない。 We can use right-to left binary method instead:

• Convert the exponent into binary form. E.g. \(87_{10} = 1010111_2\)
• If last digit of exponent is 1, then multiply base to result and square base.
• Otherwise, just square base.

Using this, it can be shown that last 20 digits of Graham's number are: \(...04575627262464195387\).

グラハム数の最後の100万桁が印刷された本が出版されている。

動画　

出典: 巨大数動画シリーズ (ニコニコ動画) - 【ゆっくりと学ぶ】グラハム数を解説してみた【再UP版】

出典: ゆっくり巨大数講座 (ニコニコ動画) - ゆっくり巨大数講座 Part(2)

プログラム

• Mitsuki1729, グラハム数 scratch巨大数選手権コンテスト, scratch.（グラハム数を計算するscratchプログラム）

関連項目

• モーザー数
• 小グラハム数
• フォークマン数