그레이엄 수

그레이엄 수(Graham's number)는 아주 큰 수의 하나이다. 이 수는 G⁶⁴(4)와 같다.

유도 방법

크누스 윗화살표 표기법을 이용하여 G(x)를 계산해 보면,

$G(1) = 3\uparrow 3 = 3^3 = 27$

$G(2) = 3\uparrow \uparrow 3 = 3\uparrow (3\uparrow \uparrow 2) = 3\uparrow (3\uparrow 3) = 3\uparrow 27 = 7,625,597,484,987$

$G(3) = 3\uparrow \uparrow \uparrow 3 = 3\uparrow \uparrow (3\uparrow \uparrow \uparrow 2) = 3\uparrow \uparrow (3\uparrow \uparrow 3) = 3\uparrow \uparrow G(2) = 3\uparrow \uparrow 7,625,597,484,987=3^{3^{3^{.^{.^.}}}}$ (7,625,597,484,987번)

$G(4) = 3\uparrow \uparrow \uparrow \uparrow 3 = 3\uparrow \uparrow \uparrow G(3) =\left.\begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{\cdot^{3}}}}}}\end{matrix}\right \}\left.\begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}\right \}\dots\left.\begin{matrix}3^{3^3}\end{matrix}\right \}3$ (G(3)번)

이렇게 급격히 증가하며, G(3)부터 이미 계산하거나 표기하기가 곤란해진다.

$G^2(4) = G(G(4)) = 3\uparrow ...\uparrow 3$ (화살표가 G(4)개, 여기서 지수는 합성 횟수를 뜻한다.)

$G^3(4) = G(G^2(4)) = 3\uparrow ...\uparrow 3$ (화살표가 G²(4)개)

...

이와 같이 증가하여 G⁶⁴(4)에 이른 것이 그레이엄 수이다.