ハイパー演算子とクヌースの矢印

足し算,かけ算,べき乗を一般化した ハイパー演算というものがある。

ハイパー演算子とは

nn を正の整数とします。

二つの正の整数 a,ba,b を受け取って一つの値を返す関数(ハイパー演算子)fn(a,b)f_n(a,b) を次のように定義します。

  • f1(a,b)=a+bf_1(a,b)=a+b

  • fn+1(a,b)f_{n+1}(a,b)bb 個の aafnf_n を順々にかましたもの

二行目の定義は厳密ではありませんが,例えば

  • fn+1(a,1)=af_{n+1}(a,1)=a

  • fn+1(a,2)=fn(a,a)f_{n+1}(a,2)=f_n(a,a)

  • fn+1(a,3)=fn(a,fn(a,a))f_{n+1}(a,3)=f_n(a,f_n(a,a))

  • fn+1(a,4)=fn(a,fn(a,fn(a,a)))f_{n+1}(a,4)=f_n(a,f_n(a,f_n(a,a)))

という感じです。

nn が小さい場合の具体例

n=1n=1 は足し算

f1(a,b)f_1(a,b)a+ba+b を返します。つまり n=1n=1 の場合のハイパー演算は足し算です。

n=2n=2 はかけ算

f2(a,2)=a+a=2af_2(a,2)=a+a=2af2(a,3)=3af_2(a,3)=3a ,などの例からも分かるように,f2(a,b)=abf_2(a,b)=ab となります。つまり n=2n=2 の場合のハイパー演算はかけ算です。

n=3n=3 はべき乗

f3(a,2)=a×a=a2f_3(a,2)=a\times a=a^2f3(a,3)=a3f_3(a,3)=a^3 ,などの例からも分かるように,f3(a,b)=abf_3(a,b)=a^b となります。つまり n=3n=3 の場合のハイパー演算はべき乗です。

n=4n=4 はテトレーション

f4(a,b)f_4(a,b) は馴染みがない演算です。 f4(a,2)=aaf_4(a,2)=a^af4(a,3)=aaaf_4(a,3)=a^{a^a} という感じです。 n=4n=4 の場合のハイパー演算をテトレーションと言います。

ちなみに階乗,二重階乗,超階乗で紹介した超階乗は f4(n!,n!)f_4(n!,n!) と書くことができます。

nn55 以上の場合はイメージすることさえ難しいです。

クヌースの矢印表記

n3n\geqq 3 に対して,fn(a,b)f_n(a,b) のことを aabb の間に上向き矢印を (n2)(n-2)並べて表記することがあります。

  • f3(a,b)=abf_3(a,b)=a\uparrow b

  • f4(a,b)=abf_4(a,b)=a\uparrow\uparrow b

  • f5(a,b)=ab=a3bf_5(a,b)=a\uparrow\uparrow\uparrow b=a\uparrow^3 b

という感じです。これをクヌースの矢印表記と言います。

計算例

計算例をいくつか確認しましょう。

  • 53=53=1255 \uparrow 3 = 5^3 = 125
  • 23=2(22)=24=162 \uparrow \uparrow 3 = 2^{(2^2)} = 2^4 = 16

計算の注意

複数の矢印があるときは右から計算します。つまり

232=232=29=29=512\begin{aligned} 2\uparrow 3 \uparrow 2 &= 2 \uparrow 3^2\\ &= 2 \uparrow 9\\ &= 2^9\\ &= 512 \end{aligned} と計算します。

グラハム数

ハイパー演算子を用いて定義される巨大な数としてグラハム数があります。

グラハム数は,数学の証明で使われたことのある最大の数としてギネスブックに掲載されています。

グラハム数の定義

正の整数 xx に対して,g(x)=3x3g(x) = 3 \uparrow^x 3 とする(x\uparrow^x\uparrowxx 本並べたもの)。

g2g^2g(g(x))g(g(x)) と定め,同様に gn(x)g^n (x)ggnn 回適用した関数とする。

グラハム数g64(4)g^{64} (4) と定義する。

グラハム数に関する定理を紹介します。

定理

nn 次元超立方体の 2n2^n 個の頂点それぞれを全て線で結ぶ。

2つの色を用意する。線を用意した2色のいずれかに塗り分ける。

このとき nn が十分大きければ(例えば nn がグラハム数ならば)、どのような塗り方をしても、同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在する。

ハイパー演算子という名前はかっこいいですが,やはり何に使うのかは分かりません。