グラハム数

グラハム数（グラハムすう、テンプレート:Lang-en-short）は、ラムゼー理論に関する未解決問題の解の推定値の上限として得られた自然数である。数学の証明で使われたことのある最大の数として1980年にギネスブックに認められた。

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

グラハム問題

3次元の立方体で同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在している例。線をどのように塗ってもこのような平面が少なくとも1つ現れてしまうのは何次元以上の超立方体か、というのがこの問題の骨子である。

この数は1970年のロナルド・グラハム、ブルース・リー・ロスチャイルドによる「グラハムの定理」 テンプレート:Cquote に関係する。つまり、n が十分大きければというが、 テンプレート:Cquote ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。

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

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

解の上限はのち2014年にミハイル・ラブロフらによってさらに小さい数が示された。

一方、この問題の解の下限（つまりこの数より小さい数では成り立たないことを示した数）としては、グラハムとロスチャイルドは1971年の小グラハム数を示したものと同じ論文中で 6 を与えた。ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、2003年にジェフ・エクスーがより良い下限として 11 を、2008年にはジェローム・バークレーが 13 を与えた。

定義

矢印表記

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

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

$x\uparrow y=x^y$

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

$x\uparrow \uparrow 1=x$

$x\uparrow \uparrow y=x\uparrow \{x\uparrow \uparrow (y-1)\}$

つまり、

$x\uparrow \uparrow y=\underset{y}{\underbrace{x\uparrow x\uparrow \cdots \uparrow x}}=\underset{y}{\underbrace{x^{x^{{\cdot }^{{\cdot }^{{\cdot }^x}}}}}}$

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

$\begin{array}{cc}3\uparrow \uparrow 2=& 3^3=27\\ 3\uparrow \uparrow 3=& 3^{3^3}=3^{27}=7625597484987\\ 3\uparrow \uparrow 4=& 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}}\\ \approx & 10^{6.0022\times 10^{3638334640023}}\end{array}$

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

$x\uparrow \uparrow \uparrow 1=x$

$x\uparrow \uparrow \uparrow y=x\uparrow \uparrow \{x\uparrow \uparrow \uparrow (y-1)\}$

つまり、

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

である。

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

$x{\uparrow }^{n}1=x$

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

グラハム数

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

$G(n)=3{\uparrow }^{n}3=3\underset{n\text{arrows}}{\underbrace{\uparrow \cdots \uparrow }}3$

と定義したときの

$\begin{array}{cc}G& =G^{64}(4)=\underset{64}{\underbrace{G(G(\cdots G}}(4)\cdots ))\\ & =\begin{array}{c}3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \uparrow \uparrow \uparrow }3\\ 3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow \uparrow \uparrow }3\text{ arrows}\\ ⋮\\ 3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots \cdots \uparrow \uparrow \uparrow }3\text{ arrows}\\ 3\uparrow \uparrow \uparrow \uparrow 3\text{ arrows}\end{array}\}64\text{ layers}\end{array}$

をグラハム数といい、その計算法は3の冪乗やテトレーションからの発展を基本としている。

その値の大きさ

テンプレート:出典の明記 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↑↑3) = 3↑↑G(2) = 3↑↑7625597484987（トリトリ）

$=\underset{\text{高 さ }7625597484987}{\underbrace{3^{3^{3^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{3^{3^3}}}}}}}}}}}}}}}}=3^{\underset{\text{高 さ }7625597484986}{\underbrace{3^{3^{3^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{3^{3^3}}}}}}}}}}}}}}}}}\approx {\exp }_{10}^{7,625,597,484,986}(1.09902)$

• G(4) = 3↑↑↑↑3 = 3→3→4 =3↑↑↑↑3 = 3↑↑↑G(3)（グラハル）

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

• G²(4) = G(G(4)) = 3↑…(G(4) 本)…↑3 = 3→3→G(4) = 3↑テンプレート:Sup3↑テンプレート:Sup…↑テンプレート:Sup3↑テンプレート:Sup3↑3↑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) = hyper(3, G⁶³(4)+2, 3) = 3↑…((G⁶³(4)+1) 本)…↑2 = 3→2→(G⁶³(4)+1) = hyper(3, G⁶³(4)+3, 2) = hyper(3, Gテンプレート:Sup(G(4))+2, 3) = hyper(3, Gテンプレート:Sup(3→2→5)+2, 3) = 3↑テンプレート:Sup3↑テンプレート:Sup…↑テンプレート:Sup3↑テンプレート:Sup3↑3↑3

G(2) までは関数電卓やパソコンでも普通に計算できるが、G(3) ですら既に3の累乗を7兆6,255億回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、テンプレート:Mathの方が遥かに大きい（しかし3↑↑↑4よりは遥かに小さい）。G(4) はその十進以下の表記が現実的に不可能な G(3) − 1 の数だけ ↑↑（二重矢印）を繰り返した数であるため、想像を絶する大きさとなっている。

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

この大きさをたとえる話として、「グラハム数を十進記数法を用いて印字しようとした場合（十分に印刷できる面積を持つ物体があるとして）、この全宇宙にある物質すべてをインクに変えても全く足りない」というものがある。しかし、その例えを使ったとしてもG(3)にすら満たない。

観測可能な宇宙の素粒子の総数は 10⁸⁰ と考えられているので、このたとえで表せる数は、素粒子1個で1文字を印刷するとしても n 進表記ならせいぜい n¹⁰⁸⁰ に過ぎない。この数は1 < | n | ≤ 16 のときグラハム数やテンプレート:Mathどころか G(3) と比較しても圧倒的に小さい（G(3) の遥か手前、$3^{3^{3^{3^3}}}$ が既におよそ ${10}^{{10}^{3.6\times {10}^{12}}}$ である）。16進表記ではアルファベットの大文字と小文字を区別しないが、Unicodeでは区別されている。現在Unicodeで使用されている文字の総数は13万7468個であり、未使用領域が全て埋め尽くされると n = 1114112となるが、 n が1億まで拡張されたとしても10^8×1080 であり、グーゴルプレックス ${10}^{{10}^{100}}$ にも満たない。

これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。宇宙論で使われた最大の数（複数の宇宙の全質量を1個のブラックホールに圧縮しそれが蒸発した後に、ポアンカレの回帰定理に従い再びブラックホールができる時間）をaとすると、aですら${10}^{{10}^{{10}^{{10}^{{10}^{1.1}}}}}\approx {10}^{{10}^{{10}^{3883775501690}}}\approx {10}^{{10}^{{10}^{{10}^{3^{2.3}}}}}\approx {10}^{{10}^{3^{3^{3^3}}}}\approx 3{\uparrow }^{2}6\in [{(3\uparrow )}^{5}2.89997,{(3\uparrow )}^{6}1.03112]$であり、これもグラハム数はおろかG(3) ともとても比較にならない。

レオナルド・サスキンドは宇宙の直径を$10^{10^{10^{122}}}$と推定しているが、この値をbとすると、bもaと同様に桁数が大きすぎて単位が考慮されていない。しかし、1辺がbヨタパーセクの立方体に1辺が1プランク長の立方体が隙間なく詰め込まれ、それらの立方体がa千年紀に渡って1プランク時間ごとに1種類の文字を生成し、作業完了時点で完全に重複する文字が1種類も存在しない場合ですら、生成された文字をc種類とし、c進法でc-1を表現する文字をc個並べた数をdとした場合、dはグラハム数はおろかG(3) ともとても比較にならない。

なお、強いて「グラハム数を十進法で表した時の桁数」を考えるなら、log₁₀Gとなるが、Gは十分な巨大数なので、この場合にあってはlog₁₀という関数で厳密には元の数より小さくなるものの、巨大数としては無視できるレベルでしかなく、近似に吸収されてしまう。すなわち、log₁₀G≒Gである。

近年は巨大数の研究・開発がより進み、現在ではグラハム数を遥かに上回る数も多数登場していて、例えばコンウェイのチェーン表記を用いて"$3\to 3\to 3\to 3$"（コンウェイのテトラトリと呼ばれる数）などと書くだけでグラハム数よりも大きな数を表現可能である。

チェーン表記を用いても G = テンプレート:Math を簡潔に表すことはできないが、次の不等式が成立する。

$3\to 3\to 64\to 2<G<3\to 3\to 65\to 2$

先述の通り、グラハム数自体は桁数を指数で表現することすら不可能なほど大きく、スーパーコンピュータでもG(3)の計算すら望めないが、末尾の数字を計算する方法は確立しており、ある程度の桁数は判明している。

テンプレート:Math を十進法で表したときの末尾10桁は テンプレート:Math であり、暗黒通信団が末尾100万桁を記した書籍も出版し、その後、暗黒通信団のウェブサイトで末尾1,600万桁を記したPDF形式のファイルも公開している。

表現

テンプレート:出典の明記 グラハム数を表すにはいくつか等価な表現がある。

• クヌースの矢印表記

$3{\uparrow }^{G^{63}(4)+1}2$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-1}3$,

$3{\uparrow }^{G^{62}\left(3{\uparrow }^{5}2\right)+1}2$,

$3{\uparrow }^{G^{62}(3\uparrow \uparrow \uparrow \uparrow \uparrow 2)+1}2$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^{3}3{\uparrow }^{2}3{\uparrow }^1[3\times \{3+(3+3)\}]$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^{3}3{\uparrow }^{2}3{\uparrow }^1\{3\times (3+6)\}$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^{3}3{\uparrow }^2{3}^3{\uparrow }^1(3+6)$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^{3}3{\uparrow }^{2}27{\uparrow }^1(3+6)$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^{3}3{\uparrow }^{2}27\uparrow 9$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^{3}3{\uparrow }^{2}3{\uparrow }^{1}27$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^{3}3{\uparrow }^2{3}^{27}$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^{3}3{\uparrow }^{2}7625597484987$,

$3{\uparrow }^{G^{63}(4)-1}3{\uparrow }^{G^{63}(4)-2}\cdots 3{\uparrow }^{6}3{\uparrow }^{5}3{\uparrow }^{4}3{\uparrow }^3\mathrm{Cg}\left(3\right)$ (テンプレート:MathはCG関数, $\mathrm{Cg}(n)=\underset{\text{長さ}n}{\underbrace{n\to n\to n\to \dots \to n\to n\to n}}$)

$\begin{array}{cc}& 3{\uparrow }^{G^{63}(4)-1}\left(3{\uparrow }^{G^{63}(4)}2\right),\\ & 3{\uparrow }^{G^{63}(4)-2}3{\uparrow }^{G^{63}(4)-1}(3{\uparrow }^{G^{63}(4)}2-1),\\ & 3\uparrow \left(3{\uparrow }^2(3{\uparrow }^3(3{\uparrow }^4(\cdots 3{\uparrow }^{G^{63}(4)-2}(3{\uparrow }^{G^{63}(4)-1}(3{\uparrow }^{G^{63}(4)-1}3-1)-1)\cdots -1)-1)-1)\right),\\ & 3\uparrow \left(3{\uparrow }^2(3{\uparrow }^3(3{\uparrow }^4(\cdots 3{\uparrow }^{G^{63}(4)-2}(3{\uparrow }^{G^{63}(4)-1}(G(G^{63}(4)-1)-1)-1)\cdots -1)-1)-1)\right),\\ & 3^{3{\uparrow }^2(3{\uparrow }^3(3{\uparrow }^4(\cdots 3{\uparrow }^{G^{63}(4)-2}(3{\uparrow }^{G^{63}(4)-1}(G(G^{63}(4)-1)-1)-1)\cdots -1)-1)-1)}\\ & \left(\begin{array}{cc}\because G(n)=3{\uparrow }^{n}3=& 3{\uparrow }^{n-1}3{\uparrow }^{n-1}3=3{\uparrow }^{n-1}G(n-1)\\ =& \underset{G(n-1)\text{個の}3}{\underbrace{3{\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}\cdots {\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}3}}\\ =& 3{\uparrow }^{n-2}\underset{(G(n-1)-1)\text{個の}3}{\underbrace{3{\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}\cdots {\uparrow }^{n-2}3{\uparrow }^{n-2}3{\uparrow }^{n-2}3}}\\ =& 3{\uparrow }^{n-2}\left(3{\uparrow }^{n-1}(G(n-1)-1)\right)\end{array}\right)\end{array}$

• コンウェイのチェーン表記

$3\to 2\to (G^{63}(4)+1),3\to 2\to (G^{62}(3\to 2\to (5))+1)$

• ハイパー演算表記

$3[G^{63}(3[6]3)+2]3,3[G^{63}(3[6]3)+3]2,3[G^{63}(3[7]2)+2]3,3[G^{63}(3[7]2)+3]2,H_{G^{63}(H_6(3,3))+2}(3,3),H_{G^{63}(H_6(3,3))+3}(3,2),H_{G^{63}(H_7(3,2))+2}(3,3),H_{G^{63}(H_7(3,2))+3}(3,2)$
$\mathrm{hyper}(3,G^{63}(\mathrm{hyper}(3,6,3))+2,3),\mathrm{hyper}(3,G^{63}(\mathrm{hyper}(3,6,3))+3,2),\mathrm{hyper}(3,G^{63}(\mathrm{hyper}(3,7,2))+2,3),\mathrm{hyper}(3,G^{63}(\mathrm{hyper}(3,7,2))+3,2)$

小グラハム数

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

$F(n)=2{\uparrow }^{n}3=2\underset{n}{\underbrace{\uparrow \cdots \uparrow }}3=2\to 3\to n$

と定義したときの

$\begin{array}{cc}F& :=F^7(12)=F\left(F\left(F\left(F\left(F\left(F(F(12))\right)\right)\right)\right)\right)\\ & =2\to 3\to (2\to 3\to (2\to 3\to (2\to 3\to (2\to 3\to (2\to 3\to (2\to 3\to 12))))))\\ & =\begin{array}{c}2\underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow }3\\ 2\underbrace{\uparrow \cdots \cdots \cdots \uparrow }3\\ \underbrace{⋮}\\ 2\underbrace{\uparrow \cdots \cdots \cdots \uparrow }3\\ 2{\uparrow }^{12}3\end{array}\}7\text{ layers}=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\\ & =2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2\to 3\to 12}3}3}3}3}3}3\\ & =2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{\mathrm{hyper}(2,14,3)}3}3}3}3}3}3\end{array}$

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

その大きさ

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

• F(1) = 2↑3 = 2→3→1 = 2→3 = 2³ = 8
• F(2) = 2↑↑3 = 2→3→2 = 2↑(2↑2) = 2↑4 = 16
• F(3) = 2↑↑↑3 = 2→3→3 = 2↑↑(2↑↑2) = 2↑↑4 = 2テンプレート:Sup = 2↑F(2) = 65536
• F(4) = 2↑↑↑↑3 = 2→3→4 = 2↑↑↑(2↑↑↑2) = 2↑↑↑4 = 2↑↑2↑↑2↑↑2 = 2↑↑F(3) = 2↑↑65536

$=\underset{65536}{\underbrace{2^{2^{2^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{{\cdot }^{2^{2^2}}}}}}}}}}}}}$

• F(5) = 2↑↑↑↑↑3 = 2→3→5 = 2↑↑↑↑2↑↑↑↑2 = 2↑↑↑↑4 = 2↑↑↑2↑↑↑2↑↑↑2 = 2↑↑↑F(4)

$=\underset{F(4)\text{ copies of }2}{\underbrace{2\uparrow \uparrow 2\uparrow \uparrow \cdots \uparrow \uparrow 2\uparrow \uparrow 2}}$

：

：

• F(12) = 2↑テンプレート:Sup3 = 2→3→12 = 2↑テンプレート:Sup2↑テンプレート:Sup2 = 2↑テンプレート:Sup4 = 2↑テンプレート:Sup2↑テンプレート:Sup2↑テンプレート:Sup2 = 2↑テンプレート:SupF(11)

$=\underset{F(11)\text{ copies of }2}{\underbrace{2{\uparrow }^{9}2{\uparrow }^9\cdots {\uparrow }^{9}2{\uparrow }^{9}2}}$

• F²(12) = F(F(12)) = 2↑…(F(12) 本)…↑3 = 2→3→F(12)

• F³(12) = 2↑…(Fテンプレート:Sup(12) 本)…↑3 = 2→3→Fテンプレート:Sup(12)

：

：

• F⁷(12) = 2↑…(Fテンプレート:Sup(12) 本)…↑3 = 2→3→Fテンプレート:Sup(12)

F(3) までは関数電卓やパソコンでも普通に計算できるが、F(4) ですら十進法以下の表記で表すことすら現実的には不可能である（ただしテンプレート:Mathよりは遥かに小さい）。同様の操作を繰り返したF(12)も同様に巨大数である。

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

グラハム数の大きさの議論と同様に、log₁₀F≒Fと見做せる。

チェーン表記を用いても F = F⁷(12) を簡潔に表すことはできないが、次の不等式が成立する。

$3\to 2\to 8\to 2<F<3\to 2\to 9\to 2$

小グラハム数もグラハム数と同様に末尾の数字を計算する方法は確立しており、ある程度の桁数は判明している。

テンプレート:Math を十進法で表したときの末尾3桁は テンプレート:Math である。

表現

小グラハム数を表すにはいくつか等価な表現がある。

• クヌースの矢印表記

$2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3}3$,

$2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-1}4$,

$2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-2}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-1}3\right)$,

$2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-2}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-3}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-4}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-5}(\cdots 2{\uparrow }^6\left(2{\uparrow }^5\left(2{\uparrow }^4\left(2{\uparrow }^3\left(2{\uparrow }^2(2\uparrow (2\cdot (2+(2+4))))\right)\right)\right)\right)\cdots )\right)\right)\right)$,

$2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-2}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-3}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-4}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-5}(\cdots 2{\uparrow }^6\left(2{\uparrow }^5\left(2{\uparrow }^4\left(2{\uparrow }^3\left(2{\uparrow }^2((2\uparrow 2)\uparrow (2+(2+4)))\right)\right)\right)\right)\cdots )\right)\right)\right)$,

$2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-2}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-3}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-4}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-5}(\cdots 2{\uparrow }^6\left(2{\uparrow }^5\left(2{\uparrow }^4\left(2{\uparrow }^3\left(2{\uparrow }^2(4\uparrow (2+(2+4)))\right)\right)\right)\right)\cdots )\right)\right)\right)$,

$2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-2}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-3}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-4}\left(2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{2{\uparrow }^{11}4}3}3}3}3}3-5}(\cdots 2{\uparrow }^6\left(2{\uparrow }^5\left(2{\uparrow }^4\left(2{\uparrow }^3\left(2{\uparrow }^2(4\uparrow 8)\right)\right)\right)\right)\cdots )\right)\right)\right)$

• コンウェイのチェーン表記

$2\to 3\to (2\to 3\to (2\to 3\to (2\to 3\to (2\to 3\to (2\to 3\to (2\to 4\to 11))))))$

これはどちらも $2\to 3\to 12=2\to 4\to 11$ を根拠としている。

ラブロフらによる解の上限

ラブロフらは2014年に、多次元三目並べに関するテンプレート:仮リンクを応用し、より小さい上限として

$N^{\prime }=2\uparrow \uparrow \uparrow 6=2\to 6\to 3=\mathrm{hyper}(2,5,6)$

を示した。これでもなお十進表記が事実上不可能なほど非常に大きい数であるが、グラハム数および小グラハム数と比較すると格段に小さい数である。これによりグラハム問題の解 n は

$\begin{array}{cc}13\le n\le 2\uparrow \uparrow \uparrow 6=& 2\to 6\to 3=\mathrm{hyper}(2,5,6)\\ =& 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2=2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 4=2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 65536\\ =& {}^{{}^{{}^{{}^{{}^{2}2}2}2}2}2={}^{{}^{{}^{{}^{4}2}2}2}2={}^{{}^{{}^{2^{2^{2^2}}}2}2}2={}^{{}^{{}^{65536}2}2}2\end{array}$

の範囲にあることになる。

関連項目

• グラハム数を超える巨大数の一覧

外部リンク

• テンプレート:MathWorld