Graham 's number - wikipedia Graham 's number This article is about the large number named after Ronald Graham. For the investing term named after Benjamin Graham, see Graham number. Graham 's number is an enormous number that arises as an upper bound on the answer of a problem in the mathematical field of Ramsey theory. It is named after mathematician Ronald Graham, who used the number as a simplified explanation of the upper bounds of the problem he was working on in conversations with popular science writer Martin Gardner. Gardner later described the number in Scientific American in 1977, introducing it to the general public. At the time of its introduction, it was the largest specific positive integer ever to have been used in a published mathematical proof. The number was published in the 1980 Guinness Book of World Records, adding to its popular interest. Other specific integers ( such as TREE ( 3 ) ) known to be far larger than Graham 's number have since appeared in many serious mathematical proofs, for example in connection with Harvey Friedman 's various finite forms of Kruskal 's theorem. Additionally, smaller upper bounds on the Ramsey theory problem from which Graham 's number derived have since been proven to be valid. Graham 's number is much larger than many other large numbers such as Skewes ' number and Moser 's number, both of which are in turn much larger than a googolplex. As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham 's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham 's number would itself be a number so large that its digital representation can not be represented in the observable universe. Nor even can the number of digits of that number. And so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe. Thus Graham 's number can not even be expressed in this way by power towers of the form a b c ⋅ ⋅ ⋅ ( displaystyle scriptstyle a ^ ( b ^ ( c ^ ( cdot ^ ( cdot ^ ( cdot ) ) ) ) ) ). However, Graham 's number can be explicitly given by computable recursive formulas using Knuth 's up - arrow notation or equivalent, as was done by Graham. As there is a recursive formula to define it, it is much smaller than typical busy beaver numbers. Though too large to be computed in full, the sequence of digits of Graham 's number can be computed explicitly through simple algorithms. The last 12 digits are : 262464195387. With Knuth 's up - arrow notation, Graham 's number is g 64 ( displaystyle g_ ( 64 ) ) where : g n = ( 3 ↑ ↑ ↑ ↑ 3, n = 1 3 ↑ g n − 1 3, n ≥ 2, n ∈ N ( displaystyle g_ ( n ) = left ( ( \begin ( matrix ) 3 \uparrow \uparrow \uparrow \uparrow 3, &n = 1 3 \uparrow ^ ( g_ ( n - 1 ) ) 3, &n geq 2, n in mathbb ( N ) end ( matrix ) ) \right. ) Contents 1 Context 2 Publication 3 Definition 3.1 Magnitude 4 Rightmost decimal digits 5 References 5.1 Bibliography 6 External links Context Example of a 2 - colored 3 - dimensional cube containing one single - coloured 4 - vertex coplanar complete subgraph. The subgraph is shown below the cube. Note that this cube would contain no such subgraph if, for example, the bottom edge in the present subgraph were replaced by a blue edge -- thus proving by counterexample that N * > 3. Graham 's number is connected to the following problem in Ramsey theory : Connect each pair of geometric vertices of an n - dimensional hypercube to obtain a complete graph on 2 vertices. Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single - coloured complete subgraph on four coplanar vertices ? In 1971, Graham and Rothschild proved that this problem has a solution N *, giving as a bound 6 ≤ N * ≤ N, with N being a large but explicitly defined number F 7 ( 12 ) = F ( F ( F ( F ( F ( F ( F ( 12 ) ) ) ) ) ) ) ( displaystyle scriptstyle F ^ ( 7 ) ( 12 ) ; = ; F ( F ( F ( F ( F ( F ( F ( 12 ) ) ) ) ) ) ) ), where F ( n ) = 2 ↑ n 3 ( displaystyle scriptstyle F ( n ) ; = ; 2 \uparrow ^ ( n ) 3 ) in Knuth 's up - arrow notation ; the number is between 4 → 2 → 8 → 2 and 2 → 3 → 9 → 2 in Conway chained arrow notation. This was reduced in 2014 via upper bounds on the Hales -- Jewett number to N ′ = 2 ↑ ↑ ↑ 6 ( displaystyle scriptstyle N ' ; = ; 2 ; \uparrow \uparrow \uparrow ; 6 ). The lower bound of 6 was later improved to 11 by Geoffrey Exoo in 2003, and to 13 by Jerome Barkley in 2008. Thus, the best known bounds for N * are 13 ≤ N * ≤ N '. Graham 's number, G, is much larger than N : f 64 ( 4 ) ( displaystyle scriptstyle f ^ ( 64 ) ( 4 ) ), where f ( n ) = 3 ↑ n 3 ( displaystyle scriptstyle f ( n ) ; = ; 3 \uparrow ^ ( n ) 3 ). This weaker upper bound for the problem, attributed to an unpublished work of Graham, was eventually published and named by Martin Gardner in Scientific American in November 1977. Publication The number gained a degree of popular attention when Martin Gardner described it in the `` Mathematical Games '' section of Scientific American in November 1977, writing that Graham had recently established, in an unpublished proof, `` a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof. '' The 1980 Guinness Book of World Records repeated Gardner 's claim, adding to the popular interest in this number. According to physicist John Baez, Graham invented the quantity now known as Graham 's number in conversation with Gardner. While Graham was trying to explain a result in Ramsey theory which he had derived with his collaborator Bruce Lee Rothschild, Graham found that the quantity now known as Graham 's number was easier to explain than the actual number appearing in the proof. Because the number which Graham described to Gardner is larger than the number in the paper itself, both are valid upper bounds for the solution to the problem studied by Graham and Rothschild. Definition Using Knuth 's up - arrow notation, Graham 's number G ( as defined in Gardner 's Scientific American article ) is G = 3 ↑ ↑ ⋯ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ 3 3 ↑ ↑ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ 3 ⋮ ⏟ 3 ↑ ↑ ⋯ ⋅ ⋅ ↑ ⏟ 3 3 ↑ ↑ ↑ ↑ 3 ) 64 layers ( displaystyle left. ( \begin ( matrix ) G& = &3 \underbrace ( \uparrow \uparrow cdots cdots cdots cdots cdots \uparrow ) 3 &&3 \underbrace ( \uparrow \uparrow cdots cdots cdots cdots \uparrow ) 3 && \underbrace ( qquad ; ; \vdots qquad ; ; ) &&3 \underbrace ( \uparrow \uparrow cdots cdot cdot \uparrow ) 3 &&3 \uparrow \uparrow \uparrow \uparrow 3 end ( matrix ) ) \right ) ( \text ( 64 layers ) ) ) where the number of arrows in each subsequent layer is specified by the value of the next layer below it ; that is, G = g 64, where g 1 = 3 ↑ ↑ ↑ ↑ 3, g n = 3 ↑ g n − 1 3, ( displaystyle G = g_ ( 64 ), ( \text ( where ) ) g_ ( 1 ) = 3 \uparrow \uparrow \uparrow \uparrow 3, g_ ( n ) = 3 \uparrow ^ ( g_ ( n - 1 ) ) 3, ) and where a superscript on an up - arrow indicates how many arrows there are. In other words, G is calculated in 64 steps : the first step is to calculate g with four up - arrows between 3s ; the second step is to calculate g with g up - arrows between 3s ; the third step is to calculate g with g up - arrows between 3s ; and so on, until finally calculating G = g with g up - arrows between 3s. Equivalently, G = f 64 ( 4 ), where f ( n ) = 3 ↑ n 3, ( displaystyle G = f ^ ( 64 ) ( 4 ), ( \text ( where ) ) f ( n ) = 3 \uparrow ^ ( n ) 3, ) and the superscript on f indicates an iteration of the function, e.g., f 4 ( n ) = f ( f ( f ( f ( n ) ) ) ) ( displaystyle scriptstyle f ^ ( 4 ) ( n ) ; = ; f ( f ( f ( f ( n ) ) ) ) ). Expressed in terms of the family of hyperoperations H 0, H 1, H 2, ⋯ ( displaystyle scriptstyle ( \text ( H ) ) _ ( 0 ), ( \text ( H ) ) _ ( 1 ), ( \text ( H ) ) _ ( 2 ), cdots ), the function f is the particular sequence f ( n ) = H n + 2 ( 3, 3 ) ( displaystyle scriptstyle f ( n ) ; = ; ( \text ( H ) ) _ ( n + 2 ) ( 3, 3 ) ), which is a version of the rapidly growing Ackermann function A ( n, n ). ( In fact, f ( n ) > A ( n, n ) ( displaystyle scriptstyle f ( n ) ; > ; A ( n, , n ) ) for all n. ) The function f can also be expressed in Conway chained arrow notation as f ( n ) = 3 → 3 → n ( displaystyle scriptstyle f ( n ) ; = ; 3 \rightarrow 3 \rightarrow n ), and this notation also provides the following bounds on G : 3 → 3 → 64 → 2 < G < 3 → 3 → 65 → 2. ( displaystyle 3 \rightarrow 3 \rightarrow 64 \rightarrow 2 < G < 3 \rightarrow 3 \rightarrow 65 \rightarrow 2. , ) Magnitude To convey the difficulty of appreciating the enormous size of Graham 's number, it may be helpful to express -- in terms of exponentiation alone -- just the first term ( g ) of the rapidly growing 64 - term sequence. First, in terms of tetration ( ↑ ↑ ( displaystyle scriptstyle \uparrow \uparrow ) ) alone : g 1 = 3 ↑ ↑ ↑ ↑ 3 = 3 ↑ ↑ ↑ ( 3 ↑ ↑ ↑ 3 ) = 3 ↑ ↑ ( 3 ↑ ↑ ( 3 ↑ ↑... ( 3 ↑ ↑ 3 )... ) ) ( displaystyle g_ ( 1 ) = 3 \uparrow \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow \uparrow ( 3 \uparrow \uparrow \uparrow 3 ) = 3 \uparrow \uparrow ( 3 \uparrow \uparrow ( 3 \uparrow \uparrow dots ( 3 \uparrow \uparrow 3 ) dots ) ) ) where the number of 3s in the expression on the right is 3 ↑ ↑ ↑ 3 = 3 ↑ ↑ ( 3 ↑ ↑ 3 ). ( displaystyle 3 \uparrow \uparrow \uparrow 3 =3 \uparrow \uparrow ( 3 \uparrow \uparrow 3 ). ) Now each tetration ( ↑ ↑ ( displaystyle scriptstyle \uparrow \uparrow ) ) operation reduces to a power tower ( ↑ ( displaystyle scriptstyle \uparrow ) ) according to the definition 3 ↑ ↑ X = 3 ↑ ( 3 ↑ ( 3 ↑... ( 3 ↑ 3 )... ) ) = 3 3 ⋅ ⋅ ⋅ 3 where there are X 3s. ( displaystyle 3 \uparrow \uparrow X =3 \uparrow ( 3 \uparrow ( 3 \uparrow dots ( 3 \uparrow 3 ) dots ) ) =3 ^ ( 3 ^ ( cdot ^ ( cdot ^ ( cdot ^ ( 3 ) ) ) ) ) quad ( \text ( where there are X 3s ) ). ) Thus, g 1 = 3 ↑ ↑ ( 3 ↑ ↑ ( 3 ↑ ↑... ( 3 ↑ ↑ 3 )... ) ) where the number of 3s is 3 ↑ ↑ ( 3 ↑ ↑ 3 ) ( displaystyle g_ ( 1 ) = 3 \uparrow \uparrow ( 3 \uparrow \uparrow ( 3 \uparrow \uparrow dots ( 3 \uparrow \uparrow 3 ) dots ) ) quad ( \text ( where the number of 3s is ) ) quad 3 \uparrow \uparrow ( 3 \uparrow \uparrow 3 ) ) becomes, solely in terms of repeated `` exponentiation towers '', g 1 = 3 3 ⋅ ⋅ ⋅ ⋅ 3 ) 3 3 ⋅ ⋅ ⋅ 3 )... 3 3 3 ) 3 where the number of towers is 3 3 ⋅ ⋅ ⋅ 3 ) 3 3 3 ) 3 ( displaystyle g_ ( 1 ) = 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 quad ( \text ( where the number of towers is ) ) quad left. ( \begin ( matrix ) 3 ^ ( 3 ^ ( cdot ^ ( cdot ^ ( cdot ^ ( 3 ) ) ) ) ) end ( matrix ) ) \right ) left. ( \begin ( matrix ) 3 ^ ( 3 ^ ( 3 ) ) end ( matrix ) ) \right ) 3 ) and where the number of 3s in each tower, starting from the leftmost tower, is specified by the value of the next tower to the right. In other words, g is computed by first calculating the number of towers, n = 3 ↑ 3 ↑ 3... ↑ 3 ( displaystyle scriptstyle n ; = ; 3 \uparrow 3 \uparrow 3 dots \uparrow 3 ) ( where the number of 3s is 3 ↑ 3 ↑ 3 = 7625597484987 ( displaystyle scriptstyle 3 \uparrow 3 \uparrow 3 ; = ; 7625597484987 ) ), and then computing the n tower in the following sequence : 1st tower : 3 2nd tower : 3 ↑ 3 ↑ 3 ( number of 3s is 3 ) = 7625597484987 3rd tower : 3 ↑ 3 ↑ 3 ↑ 3 ↑... ↑ 3 ( number of 3s is 7625597484987 ) =... ⋮ g = n tower : 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑... ↑ 3 ( number of 3s is given by the n - 1 tower ) where the number of 3s in each successive tower is given by the tower just before it. Note that the result of calculating the third tower is the value of n, the number of towers for g. The magnitude of this first term, g, is so large that it is practically incomprehensible, even though the above display is relatively easy to comprehend. Even n, the mere number of towers in this formula for g, is far greater than the number of Planck volumes ( roughly 10 of them ) into which one can imagine subdividing the observable universe. And after this first term, still another 63 terms remain in the rapidly growing g sequence before Graham 's number G = g is reached. To illustrate just how fast this sequence grows, while g is equal to 3 ↑ ↑ ↑ ↑ 3 ( displaystyle 3 \uparrow \uparrow \uparrow \uparrow 3 ) with only four up arrows, the number of up arrows in g is this incomprehensibly large number g. Rightmost decimal digits Graham 's number is a `` power tower '' of the form 3 ↑ ↑ n ( with a very large value of n ), so its rightmost decimal digits must satisfy certain properties common to all such towers. One of these properties is that all such towers of height greater than d ( say ), have the same sequence of d rightmost decimal digits. This is a special case of a more general property : The d rightmost decimal digits of all such towers of height greater than d + 2, are independent of the topmost `` 3 '' in the tower ; i.e., the topmost `` 3 '' can be changed to any other non-negative integer without affecting the d rightmost digits. The following table illustrates, for a few values of d, how this happens. For a given height of tower and number of digits d, the full range of d - digit numbers ( 10 of them ) does not occur ; instead, a certain smaller subset of values repeats itself in a cycle. The length of the cycle and some of the values ( in parentheses ) are shown in each cell of this table : Number of different possible values of 3 ↑ 3 ↑... 3 ↑ x when all but the rightmost d decimal digits are ignored Number of digits ( d ) 3 ↑ x 3 ↑ 3 ↑ x 3 ↑ 3 ↑ 3 ↑ x 3 ↑ 3 ↑ 3 ↑ 3 ↑ x 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ x ( 1, 3, 9, 7 ) ( 3, 7 ) ( 7 ) ( 7 ) ( 7 ) 20 ( 01, 03,..., 87,..., 67 ) ( 03, 27, 83, 87 ) ( 27, 87 ) ( 87 ) ( 87 ) 100 ( 001,003,..., 387,..., 667 ) 20 ( 003,027,... 387,..., 587 ) ( 027,987,227, 387 ) ( 987, 387 ) ( 387 ) The particular rightmost d digits that are ultimately shared by all sufficiently tall towers of 3s are in bold text, and can be seen developing as the tower height increases. For any fixed number of digits d ( row in the table ), the number of values possible for 3 ↑ ( displaystyle scriptstyle \uparrow ) 3 ↑... 3 ↑ x mod 10, as x ranges over all nonnegative integers, is seen to decrease steadily as the height increases, until eventually reducing the `` possibility set '' to a single number ( colored cells ) when the height exceeds d + 2. A simple algorithm for computing these digits may be described as follows : let x = 3, then iterate, d times, the assignment x = 3 mod 10. Except for omitting any leading 0s, the final value assigned to x ( as a base - ten numeral ) is then composed of the d rightmost decimal digits of 3 ↑ ↑ n, for all n > d. ( If the final value of x has fewer than d digits, then the required number of leading 0s must be added. ) Let k be the numerousness of these stable digits, which satisfy the congruence relation G ( mod 10 ) ≡ ( G ) ( mod 10 ). k = t - 1, where G ( t ) : = 3 ↑ ↑ t. It follows that, g ≪ k ≪ g. The algorithm above produces the following 500 rightmost decimal digits of Graham 's number ( or of any tower of more than 500 3s ) :... 02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780 38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387 References Jump up ^ `` Graham 's number records ''. Iteror.org. Retrieved 2014 - 04 - 09. Jump up ^ Lavrov, Mikhail ; Lee, Mitchell ; Mackey, John ( 2014 ). `` Improved upper and lower bounds on a geometric Ramsey problem ''. European Journal of Combinatorics. 42 : 135 -- 144. doi : 10.1016 / j. ejc. 2014.06. 003. Jump up ^ Exoo, Geoffrey ( 2003 ). `` A Euclidean Ramsey Problem ''. Discrete & 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. Jump up ^ Barkley, Jerome ( 2008 ). `` Improved lower bound on an Euclidean Ramsey problem ''. arXiv : 0811.1055 ( math.CO ). Jump up ^ Martin Gardner ( 1977 ) `` In which joining sets of points leads into diverse ( and diverting ) paths ''. Scientific American, November 1977 Jump up ^ John Baez ( 2013 ). `` A while back I told you about Graham 's number... '' Jump up ^ `` The Math Forum @ Drexel ( '' Last Eight Digits of Z `` ) ''. Mathforum.org. Retrieved 2014 - 04 - 09. Jump up ^ Ripà, Marco ( 2011 ). La strana coda della serie n ^ n ^... ^ n ( in Italian ). UNI Service. ISBN 978 - 88 - 6178 - 789 - 6. Bibliography 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. 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 ''. In Rota, G-C. Studies in Combinatorics ( MAA Studies in Mathematics ). 17. Mathematical Association of America. pp. 80 -- 99. ISBN 0 - 88385 - 117 - 2. On p. 90, in stating `` the best available estimate '' for the solution, the explicit formula for N is repeated from the 1971 paper. External links Sbiis Saibian 's article on Graham 's number `` A Ramsey Problem on Hypercubes '' by Geoff Exoo Mathworld article on Graham 's number How to calculate Graham 's number Conceptualizing 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. Ron Graham. `` What is Graham 's Number ? ( feat Ron Graham ) '' ( video ). Numberphile. Brady Haran. Ron Graham. `` How Big is Graham 's Number ? ( feat Ron Graham ) '' ( video ). Numberphile. Brady Haran. The last 16 million digits of Graham 's number by the Darkside communication group Large numbers Examples in numerical order Thousand Ten thousand Hundred thousand Million Ten million Hundred million Billion Trillion Quadrillion Quintillion Sextillion Septillion Googol Googolplex Skewes 's number Googolduplex Moser 's number Graham 's number TREE ( 3 ) SSCG ( 3 ) Rayo 's number Transfinite numbers Expression methods Notations Knuth 's up - arrow notation Conway chained arrow notation Steinhaus -- Moser notation Operators Hyperoperation Tetration Pentation Ackermann function Bowers 's operators Related articles Infinitesimal Number systems Number names Orders of magnitude List of notable numbers Indefinite and fictitious numbers Extended real number line Power of two Power of 10 Long and short scales Titanic prime Gigantic prime Megaprime Largest known prime number Names History Retrieved from `` https://en.wikipedia.org/w/index.php?title=Graham%27s_number&oldid=817431712 '' Categories : Ramsey theory Integers Large integers Hidden categories : CS1 Italian - language sources ( it ) Talk Contents About Wikipedia Asturianu Български Čeština Dansk Deutsch Ελληνικά Español Esperanto Français 한국어 Italiano עברית Lumbaart Magyar Bahasa Melayu Nederlands 日本 語 Norsk Polski Português Русский Simple English Slovenčina Suomi Svenska ไทย Türkçe Українська 中文 Edit links This page was last edited on 28 December 2017, at 09 : 44. Text is available under the Creative Commons Attribution - ShareAlike License ; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia ® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. About Wikipedia

Question: what is the value of graham's number
Answer: n