그레이엄 수

또 다른 그레이엄 수에 대해서는 벤저민 그레이엄 수 문서를 참고하십시오.

그레이엄 수(Graham's number)는 미국의 수학자 로널드 그레이엄이 이름을 붙인 특정한 자연수의 명칭으로서, 수학적으로 의미를 가지고 있는 가장 큰 자연수이다. $G^{64}(4)$로 표시한다. 램지 이론에 대한 수학 문제의 해결과정에서 상계(upper bound)로 제시한 수로서, 단순한 크기 이외의 수학적 의미를 갖는 수 가운데 가장 큰 수라는 의의를 갖고 있으며, 기네스북에도 실려 있다. 그 크기는 너무나 거대해서 자연계 또는 물리적인 실체, 또는 문학적 비유나 상상 등으로조차도 비견될 만한 존재가 없다. 일상적인 자연수 표기법이나 거듭제곱의 방법으로는 도저히 나타낼 수 없어서, 특수하게 정의된 큰 수 표기법을 사용하여 나타낸다. 이 수 전체는 아직까지 계산된 적도, 또한 그렇게 계산된 수를 나열하는 것도 불가능하다. 다만, 계산 과정에 규칙성이 있기 때문에 1의 자리부터 마지막 500자리까지의 수는 알려져 있다. 이름이 붙어있는 수 가운데 그레이엄 수보다 더 큰 수는 있으나, 수학적 또는 물리적 의의는 없다.

문제

한개의 평면 완전부분그래프를 가진 2색 3차원 그래프. 부분 그래프는 아래에 그려졌다. 만약 이 부분그래프의 바닥 모서리를 파란색으로 바꾼다면 한개의 색을 가진 네 꼭짓점 평면 완전 그래프는 없다. 따라서 N* > 3이다.

N차원 초입방체의 모서리, 모든 대각선을 포함한 완전 그래프 $K_{N}$을 그린다. 그래프의 변을 두 가지 색으로 칠할 때, 몇 차원 이상이 되면 초입방체의 한평면에 있는 4개의 점에 대해서 4 개 꼭짓점을 이은 완전 그래프 $K_{4}$는 하나의 색으로 되어 있다. 그레이엄은 이 N의 상계로서 그레이엄의 수를 제시하였다.

유도 방법

그레이엄 수의 기본은 3이다. 3을 밑으로 하여 3의 연산을 무수히 반복하는 과정이 되풀이된다. 이 연산을 나타내기 위해서 커누스 윗화살표 표기법의 이해가 필요하다. 커누스 윗화살표 표기법은 하이퍼연산자라고도 하며, 덧셈-곱셈-거듭제곱-테트레이션-펜트레이션-....등으로 그 직전 연산의 반복으로 상위 연산을 정의하는 기호이다. 커누스 윗화살표 표기법을 이용하여 G(x)를 계산해 보면,

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

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

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

$G(4)=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow \uparrow G(3)=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow ...(3\uparrow \uparrow (3\uparrow \uparrow 3))...))$   (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^{\cdot ^{\cdot ^{3}}}}\end{matrix}}\right\}\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}(4)=G(G^{3}(4))=3\uparrow ...\uparrow 3$ (화살표가 G³(4)개)

...

$G^{63}(4)=G(G^{62}(4))=3\uparrow ...\uparrow 3$ (화살표가 G⁶²(4)개)

$G^{64}(4)=G(G^{63}(4))=3\uparrow ...\uparrow 3$ (화살표가 G⁶³(4)개)

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

결과

그레이엄 수는 너무 크기 때문에 10진수로 표기하는 것이 불가능하지만, 마지막 500자리의 수는 다음과 같이 알려져 있다.

 …02425950695064738395657479136519351798334535362521
  43003540126026771622672160419810652263169355188780
  38814483140652526168785095552646051071172000997092
  91249544378887496062882911725063001303622934916080
  25459461494578871427832350829242102091825896753560
  43086993801689249889268099510169055919951195027887
  17830837018340236474548882222161573228010132974509
  27344594504343300901096928025352751833289884461508
  94042482650181938515625357963996189939679054966380
  03222348723967018485186439059104575627262464195387

수의 규모

• 그레이엄 수를 아주 작은 1포인트 크기로 인쇄하더라도, 그 수의 전체 길이는 우주의 직경보다 더 크다.
• 그레이엄 수를 1초에 10글자씩 빠르게 적더라도, 우주의 나이보다 더 오랜 시간이 필요하다.
• 그레이엄 수는 우주에 존재하는 모든 소립자의 개수보다 더 크다.

더 보기

• 큰 수
• 커누스 윗화살표 표기법
• 하이퍼 연산
• 아커만 함수
• 램지의 정리

참고 문헌

• Graham, R. L.; Rothschild, B. L. (1971). “Ramsey's Theorem for n-Parameter Sets” (PDF). 《Transactions of the American Mathematical Society》 159: 257–292. doi:10.2307/1996010. JSTOR 1996010.  The explicit formula for N appears on p. 290. This is not the "Graham's number" G published by Martin Gardner.
• Graham, R. L.; Rothschild, B.L. (1978). "Ramsey Theory", Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America, 17:80–99. On p. 90, in stating "the best available estimate" for the solution, the explicit formula for N is repeated from the 1971 paper.
• Gardner, Martin (November 1977). “Mathematical Games” (PDF). 《Scientific American》 237: 18–28. doi:10.1038/scientificamerican1177-18. ; reprinted (revised) in Gardner (2001), cited below.
• Gardner, Martin (1989). 《Penrose Tiles to Trapdoor Ciphers》. Washington, D.C.: Mathematical Association of America. ISBN 0-88385-521-6. 
• Gardner, Martin (2001). 《The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems》. New York, NY: Norton. ISBN 0-393-02023-1. 
• Exoo, Geoffrey (2003). “A Euclidean Ramsey Problem”. 《Discrete and Computational Geometry》 29 (2): 223–227. doi:10.1007/s00454-002-0780-5.  Exoo refers to the Graham & Rothschild upper bound N by the term "Graham's number". This is not the "Graham's number" G published by Martin Gardner.
• Barkley, Jerome (2008). “Improved lower bound on an Euclidean Ramsey problem”. arXiv:0811.1055v1 [math.CO]. 

바깥 고리

• "A Ramsey Problem on Hypercubes" by Geoff Exoo
• Mathworld article on Graham's number
• How to calculate Graham's number
• Some Ramsey results for the n-cube prepublication mentions Graham's number
• Padilla, Tony; Parker, Matt. “Graham's Number”. 《Numberphile》. Brady Haran. 

십진수

10n	수	한자(영어)	십진수
G64(4)	그레이엄 수	Graham's number	계산 및 표기 불가능 (단, 1의 자리부터 마지막 500자리까지의 수는 알려져 있음) ...03222348723967018485186439059104575627262464195387
10100!	구골뱅	Googolbang	구골! = 10100! = 1 x 2 x 3 x 4 x ... x (구골-2) x (구골-1) x 구골
(1010100)1010100	FZ구골플렉스	Fzgoogolplex	구골플렉스구골플렉스 = (1010100)구골플렉스 = 구골플렉스1010100
101010100	구골플렉시안	Googolplexian	10구골플렉스 = 1010구골
(10010100)2	가구골플렉스	Gargoogolplex	(10010100)2 = 구골플렉스2
1010100	구골플렉스	Googolplex	10구골 = 1010100
10600	센틸리언	Centillion	10600 = (10100)6 = 구골6
10100	구골	Googol	10100
1068	무량대수	無量大數	100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
1064	불가사의	不可思議	10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
1060	나유타	那由他	1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
1056	아승기	阿僧祇	100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
1052	항하사	恒河沙	10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
1048	극	極	1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
1044	재	載	100,000,000,000,000,000,000,000,000,000,000,000,000,000,000
1040	정	正	10,000,000,000,000,000,000,000,000,000,000,000,000,000
1036	간	澗	1,000,000,000,000,000,000,000,000,000,000,000,000
1032	구	溝	100,000,000,000,000,000,000,000,000,000,000
1028	양	壤	10,000,000,000,000,000,000,000,000,000
1024	자	秭	1,000,000,000,000,000,000,000,000
1020	해	垓	100,000,000,000,000,000,000
1016	경	京	10,000,000,000,000,000
1012	조	兆	1,000,000,000,000
108	억	億	100,000,000
104	만	萬	10,000
103	천	千	1,000
102	백	百	100
101	십	十	10
100	일	一	1
10-1	분	分	0.1
10-2	리	厘，釐	0.01
10-3	모, 호	毛，毫	0.001
10-4	사	絲	0.0001
10-5	홀	忽	0.00001
10-6	미	微	0.000001
10-7	섬	纖	0.0000001
10-8	사	沙	0.00000001
10-9	진	塵	0.000000001
10-10	애	埃	0.0000000001
10-11	묘	渺	0.00000000001
10-12	막	漠	0.000000000001
10-13	모호	模糊	0.0000000000001
10-14	준순	逡巡	0.00000000000001
10-15	수유	須臾	0.000000000000001
10-16	순식	瞬息	0.0000000000000001
10-17	탄지	彈指	0.00000000000000001
10-18	찰나	刹那	0.000000000000000001
10-19	육덕	六德	0.0000000000000000001
10-20	허공	虛空	0.00000000000000000001
10-21	청정	淸淨	0.000000000000000000001