グラハム数

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/05/02 16:40 UTC 版)

極めて巨大な巨大数であり指数で表記するのは事実上不可能なため特別な表記法を用いて表される。

グラハム問題

この数は、1970年のロナルド・グラハム（英語版）とブルース・リー・ロスチャイルド（英語版）による「グラハムの定理」

“

n 次元超立方体の 2ⁿ 個の頂点のそれぞれを互いに全て線で結ぶ。次に2つの色を用いて連結した線をいずれかの色に塗り分ける。
このとき n が十分大きければ、どんな塗り方をしても、同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在する。

”

に関係する。つまり、n が十分大きければというが、

“

n がいくらより大きければ、この関係は常に成立するか

”

ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。

しかし、この関係がグラハム数以上の n について成り立つことがグラハム自身によって証明された。つまり、解はグラハム数以下である。

ただしグラハムらは実際にはこの数を論文では発表しておらず、翌1971年にグラハム数より小さなグラハム問題の解の上限として、小グラハム数という数を発表した^[2]。その後、マーティン・ガードナーが1977年にサイエンティフィック・アメリカンでグラハム数を紹介した^[3]ことによってこの数は広く知られるようになった。

グラハムとロートシルトは1971年の小グラハム数を示したものと同じ論文中で解の下限として 6 を与えた。ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、Geoff Exoo は2003年により良い下限として 11 を与えた^[4]。

定義

矢印表記

グラハム数は巨大すぎて、通常の指数では事実上表現不可能である。そのため次のような特殊な関数を用いる。

まず、クヌースの矢印表記を使い、x, y を自然数としたとき、演算子「↑」を次のように定義する。

x \uparrow y = x ^ y

さらに「↑↑」を次のように再帰的に定義する。

x \uparrow\uparrow 1 = x

x \uparrow\uparrow y = x \uparrow \left\{x \uparrow\uparrow \left(y - 1\right)\right\}

つまり、

x\uparrow\uparrow y =\ \underbrace{x\uparrow x\uparrow \cdots \uparrow x}_y = \underbrace{x^{x^{\cdot^{\cdot^{\cdot^x}}}}}_{y}

となる（ $\underbrace{}_y$ は、x が y 個あることを表す）。ただし演算は右から行う。つまり例えば、x↑x↑x = x↑(x↑x) である。例を挙げると次のようになる。

\begin{align} 3\uparrow\uparrow2=&3^3=27 \\ 3\uparrow\uparrow3=&3^{3^3}=3^{27}=7625597484987 \\ 3\uparrow\uparrow4=&3^{3^{3^3}}=3^{7625597484987}\\ \approx &1.258\times 10^{3638334640024} \\ 3 \uparrow\uparrow 5=&3^{3^{3^{3^3}}}=3^{3^{7625597484987}}\\ \approx &3^{1.258\times 10^{3638334640024}}\end{align}

同様に「↑↑↑」を次のように再帰的に定義する。

x \uparrow\uparrow\uparrow 1 = x

x \uparrow\uparrow\uparrow y = x \uparrow\uparrow \left\{x \uparrow\uparrow\uparrow (y - 1)\right\}

つまり、

x\uparrow\uparrow\uparrow y = \underbrace{x\uparrow\uparrow x\uparrow\uparrow \cdots \uparrow\uparrow x}_{y\text{ copies of }x}

である。

一般の場合も同様に、「↑…(n 本)…↑」＝「↑ⁿ」を次のように定義する。

x \uparrow^n 1 = x

x \uparrow^n y = x \uparrow^{n-1} \left\{x \uparrow^n \left(y - 1 \right)\right\}

グラハム数

これを用いて、関数 G(n) を

G(n) = 3 \uparrow^n 3

と定義したときの

\begin{align} G &= G^{64} (4) = \underbrace{G(G(\cdots G}_{64} (4) \cdots ))\\ &= \left. \begin{matrix} 3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \cdots \cdots \uparrow}3 \\ 3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\ \underbrace{\qquad\;\; \vdots \qquad\;\;} \\ 3\underbrace{\uparrow \uparrow \cdots\cdots \uparrow}3 \\ 3\uparrow \uparrow \uparrow \uparrow3 \end{matrix} \right \} 64 \text{ stages} \end{align}

をグラハム数と言う。

その大きさ

G(x) を実際に計算してみると、

G(1) = 3↑3 = 3→3→1 = 3→3 = 3³ = 27
G(2) = 3↑↑3 = 3→3→2 = 3↑(3↑3) = 3↑G(1) = 3↑27 = 7625597484987
G(3) = 3↑↑↑3 = 3→3→3 = 3↑↑(3↑↑3) = 3↑↑G(2) = 3↑↑7625597484987

= \underbrace{3^{3^{3^{ \cdot ^{ \cdot^ { \cdot^ { \cdot^ { \cdot^ { \cdot^ {\cdot^ { \cdot^ { \cdot^ { \cdot^ { 3^{ 3^ 3}}}}}}}}}}}}}}}_{7625597484987}

G(4) = 3↑↑↑↑3 = 3→3→4 = 3↑↑↑G(3)

=\underbrace{3\uparrow\uparrow 3\uparrow\uparrow \cdots \uparrow\uparrow 3 \uparrow\uparrow 3 }_{G(3) \text{ copies of }3 }

G²(4) = G(G(4)) = 3↑…(G(4) 本)…↑3 = 3→3→G(4)

G³(4) = G(G²(4)) = 3↑…(G²(4) 本)…↑3 = 3→3→G²(4)

：

G⁶⁴(4) = G(G⁶³(4)) = 3↑…(G⁶³(4) 本)…↑3 = 3→3→G⁶³(4) = hyper(3, G⁶³(4)+2, 3)

G(2) までは十進法表記で表すことができるが、G(3) ですら既に3の累乗を7兆6000億回以上繰り返した数であるため、現実の何物とも比べられないような巨大数になっており、後述するように十進法表記で表すことすら現実的には不可能である。G(4) はその十進表記が現実的に不可能な G(3) − 1 の数だけ ↑↑（二重矢印）を繰り返した数であるため、想像を絶する大きさとなっている。

次の段階の G²(4) は3と3の間に G(4) 本矢印をおいたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 ( $2\left[ 2[5] \right ]=2 \left[2[4][4] \right]$ )も超える。この操作を63回繰り返した数がグラハム数である。

この大きさをたとえる話として、「グラハム数を十進記数法を用いて印字しようとした場合（十分に印刷できる面積を持つ物体があるとして）、この全宇宙にある物質すべてをインクに変えても全く足りない」というものがある。しかし、観測可能な宇宙の素粒子の総数は 10⁸⁰ と考えられているので、このたとえで表せる数は、粒子1個で1文字を印刷するとしてもせいぜい 10^10⁸⁰ に過ぎない。この数はグラハム数どころか G(3) と比較しても圧倒的に小さく（G(3) の遥か手前、 $3^{3^{3^{3^{3}}}}$ が既に約 $10^{10^{3.6\times10^{12}}}$ である）、グーゴルプレックス $10^{10^{100}}$ にも満たない。これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。

コンウェイのチェーン表記を用いても G = G⁶⁴(4) を簡潔に表すことは出来ないが、次の不等式が成立する。

3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2

ちなみに、グラハム数を十進法で表したときの下3桁は387である。

小グラハム数

グラハムとロートシルトは1971年に、より小さい上限として小グラハム数 (Little Graham) を示した。この数は関数 F(n) を

F(n) = 2 \uparrow^{n} 3 =2\underbrace{\uparrow \cdots \uparrow}_{n}3 = 2 \rightarrow 3 \rightarrow n

と定義したときの

\begin{align} F &:= F^{7} (12) = F \left(F \left(F \left (F \left (F \left (F \left(F(12) \right) \right ) \right) \right ) \right ) \right)\\ &= \left. \begin{matrix} 2\underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow}3 \\ 2\underbrace{\uparrow \cdots \cdots \cdots \uparrow}3 \\ \underbrace{\qquad\;\; \vdots \qquad\;\;} \\ 2\underbrace{\uparrow \cdots \cdots \cdots \uparrow}3 \\ 2\uparrow^{12}3 \end{matrix} \right \}7\text{ stages} = 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 12 } 3 } 3 } 3 } 3 } 3 } 3 } 3 = 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow 3 } 3 } 3 } 3 } 3 } 3 } 3 \end{align}

である。これはグラハム数よりは遥かに小さいが、それでもなお非常に大きい数である。

表・話・編・歴

巨大数

数の例

百万 · グーゴル · 不可説不可説転 · グーゴルプレックス · グーゴルプレックスプレックス · スキューズ数 · モーザー数 · グラハム数 · 無限

表現法

表記	クヌースの矢印表記 · コンウェイのチェーン表記 · 多角形表記

演算子	ハイパー演算子（テトレーション,ペンテーション） · アッカーマン関数 · 超階乗

	ダイバーシティ
	塩対応
	コミット
	ナレ死
	語彙力
	赤口
	所信表明
	フェチ
	あざとい
	たぎり

11	吝かではない
12	注意喚起
13	コンプライアンス
14	つきましては
15	ご容赦ください
16	国民の三大義務
17	ご教示
18	鑑みる
19	レスポンシビリティ
20	汎用性

21	一両日中
22	按分
23	インセンティブ
24	遅ればせながら
25	十柱戯
26	高じる
27	御贔屓
28	ご用命
29	総花的
30	こざとへん

グラハム数グラハム数の概要

グラハム数

目次

グラハム問題

定義

矢印表記

グラハム数

その大きさ

小グラハム数

「グラハム数」の関連用語

画像から探す

グラハム数 グラハム数の概要

グラハム数

目次

グラハム問題

定義

矢印表記

グラハム数

その大きさ

小グラハム数

「グラハム数」の関連用語

画像から探す

グラハム数グラハム数の概要