그레이엄 수

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

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

문제[편집]

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

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

유도 방법[편집]

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

  (G(2)번 반복) (7,625,597,484,987번 반복)

  (G(3)번 반복)
            (G(3)번 반복)

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

(화살표가 G(4)개, 여기서 지수는 합성 횟수를 뜻한다.)

(화살표가 G2(4)개)

(화살표가 G3(4)개)

...

(화살표가 G62(4)개)

(화살표가 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” (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]. 

바깥 고리[편집]

십진수
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