- 他の用法については、グラハム数 (曖昧さ回避) をご覧ください。
グラハム数を矢印表記にするとこのようになる。
グラハム数 (Graham's number) は、Ronald Grahamが定義した有名な巨大数[1]である。
矢印表記を使って、このように定義出来る。
\[\begin{eqnarray*} G_0 &=& 4 \\ G_1 &=& 3 \underbrace{\uparrow\uparrow\uparrow\uparrow}_{G_0=4} 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)=\underbrace{G(G( \cdots G(}_{64}4)\cdots))\)である。
グラハム数は数学の証明で使われた最大の数としてギネスブックにも登録されている。ちなみに、「数学的に意味のある」巨大数に関しては、TREE(3)、SCG(13)等、グラハム数より遥かに巨大なものが存在する。
巨大数漫画「寿司 虚空編」[2]では、第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 K4 of one color with coplanar vertices will be forced. Find N*.
グラハムは、この問題の答えが存在する事を証明する論文を発表し、その値の上限を \(F(n) = 2 \uparrow^{n} 3\) (矢印表記を使用)としたときの\(F^{7}(12)\)であるとした[3]。Sbiis Saibian は、この数を"小グラハム数"と呼んだ。グラハム数は、この論文の前に未公表の論文に書かれていたことがあり、マーティン・ガードナーがサイエンティフィック・アメリカンにそのことを書いた[4]ことで有名になった。
ガードナーの記事には小さなミスがあり、\(3\uparrow\uparrow7625597484987=3\uparrow(7625597484987\uparrow7625597484987)\)であると書かれているが、実際には \(3 \uparrow (3\uparrow\uparrow7625597484986)\)である。
比較[]
\(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 は、グラハム数がモーザー数よりもはるかに大きい事を証明した[5]。 この証明は、スタインハウス・モーザー表記で(k + 2)角形の中の nは \(n\underbrace{\uparrow\uparrow\ldots\uparrow\uparrow}_{2k-1}n\) よりも小さいことを利用している。彼はこの証明を Susan Stepney に1998年7月7日に送った[6]。 偶然にも、Stepney は Todd Cesere から同様の証明を数日後に受け取った。
グラハム数はビジービーバー関数の\(\Sigma(64)\)よりもずっと小さいことが証明されている[7]。Googology WikiユーザーのWythagorasによると、Wythagorasは同じくGoogology WikiユーザーであるDeedlit11によるチューリングマシンを改良することで、\(\Sigma(18) > G\)を導くようなチューリングマシンを発見したと主張し、厳密な証明の代わりに証明のスケッチを公開した[8]。
グラハム数は\(f_{\omega+1}(64)\)よりも小さいことがふぃっしゅによって証明されている[9]。
最後の桁の計算[]
グラハム数は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。
- 以下同様にして求められる。
このアルゴリズムは完全ではない。グラハム数はある整数\(k\)をつかって\(3\uparrow\uparrow k\)と表されるが、\(x < k\)の範囲でしか有効でない。
左端の表記を計算した時の桁数は指数的に増えるので、この単純なやり方はあまり効率的ではない。実用的には繰り返し2乗法とモジュロ演算を組み合わせることで計算できる。
Using this, it can be shown that last 20 digits of Graham's number are: \(...04575627262464195387\).[10]
グラハム数の最後の100万桁が印刷された本が出版されている[11]。
動画[]
出典: 巨大数動画シリーズ (ニコニコ動画) - 【ゆっくりと学ぶ】グラハム数を解説してみた【再UP版】
出典: ゆっくり巨大数講座 (ニコニコ動画) - ゆっくり巨大数講座 Part(2)
プログラム[]
- Mitsuki1729, グラハム数 scratch巨大数選手権コンテスト, scratch.（グラハム数を計算するscratchプログラム）
出典[]
- ↑ Graham's Number
- ↑ 裏サンデー 寿司 虚空編
- ↑ Graham, R. L. and Rothschild, B. L. "Ramsey's Theorem for n-Parameter Sets." Trans. Amer. Math. Soc. 159, 257-292, 1971.
- ↑ Gardner, M. (1977) "Mathematical games: In which joining sets of points leads into diverse (and diverting) paths" Scientific American 237(5), 18-28. doi:10.1038/scientificamerican1177-18.
- ↑ G >> Mの証明 (このサイトでは、 n[m] = スタインハウス・モーザー表記でm角形の中の n である。)
- ↑ Stepney, Susan. Moser's polygon notation. Retrieved 2013-03-17.
- ↑ Proof that BB(64) >> G
- ↑ en:User blog:Wythagoras/The nineteenth Busy Beaver number is greater than Graham's Number!
- ↑ Fish. Upper bound of Graham's number in fast-growing hierarchy, July 11, 2021.
- ↑ Last 10000 digits of G
- ↑ TokusiN (2017) グラハム数1,000,000桁表〈最終巻〉 暗黒通信団