그레이엄 수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

그레이엄 수(Graham's number)는 미국수학자 로널드 그레이엄이 이름붙인 특정 자연수의 명칭이다. 램지 이론에 대한 수학 문제의 해결과정에서 상계(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 (화살표가 G2(4)개)

G^4(4) = G(G^3(4)) = 3\uparrow ...\uparrow 3 (화살표가 G3(4)개)

...

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

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

이와 같이 증가하여 G64(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”. 《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”. 《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.

바깥 고리[편집]

십진수
v  d  e  h
10n 한자(영어) 십진수
G64(4) 그레이엄 수 Graham's number 계산 및 표기 불가능. (단, 1의 자리부터 마지막 500자리까지의 수는 알려져 있음) ...03222348723967018485186439059104575627262464195387
101010100 구골플렉시안 Googolplexian 10구골플렉스 = 1010구골 = 101010,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
1010100 구골플렉스 Googolplex 10구골 = 1010,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
10100 구골 Googol 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
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