FANDOM


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

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

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

\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 ↑n 3 としたときの g64(4) である。

グラハム数は数学の証明で使われた最大の数としてギネスブックにも登録されている。ちなみに、「数学的に意味のある」巨大数に関しては、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 nN*, 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↑↑7625597484987 = 3↑(7625597484987↑7625597484987)であると書かれているが、実際には3↑(3↑↑7625597484986) である。

比較 編集

g0 が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]。さらに、グラハム数は \(\Sigma(22)\) よりも小さい事が証明されている[8]

最後の桁の計算 編集

グラハム数は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\).[9]

動画 編集

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

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

出典 編集

  1. Graham's Number
  2. 裏サンデー 寿司 虚空編
  3. Graham, R. L. and Rothschild, B. L. "Ramsey's Theorem for n-Parameter Sets." Trans. Amer. Math. Soc. 159, 257-292, 1971.
  4. 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.
  5. G >> Mの証明 (このサイトでは、 n[m] = スタインハウス・モーザー表記m角形の中の n である。)
  6. Stepney, Susan. Moser's polygon notation. Retrieved 2013-03-17.
  7. Proof that BB(64) >> G
  8. en:User_blog:Wythagoras/NEWS! I found a 22-state machine that beats G!
  9. Last 10000 digits of G

関連項目 編集

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。