Graham's number
Graham's number is an immense number that arose as an upper bound on the answer of a problem in the mathematical field of Ramsey theory. It is much larger than many other large numbers such as Skewes's 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 cannot 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 cannot be expressed even by physical universe-scale power towers of the form formula_1. 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 thirteen digits are ...7262464195387. With Knuth's up-arrow notation, Graham's number is formula_2, where formula_3 Graham's number is named after the American mathematician Ronald Graham, who used the number in conversations with popular science writer Martin Gardner as a simplified explanation of the upper bounds of the problem he was working  on. In 1977, Gardner described the number in "Scientific American", 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 described 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. Context. Graham's number is connected to the following problem in Ramsey theory: In 1971, Graham and Rothschild proved the Graham–Rothschild theorem on the Ramsey theory of parameter words, a special case of which shows that this problem has a solution "N*". They bounded the value of "N*" by 6 ≤ "N*" ≤ "N", with "N" being a large but explicitly defined number where formula_5 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 which contains three tetrations. In 2019 this was further improved to: 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 . Graham's number, "G", is much larger than "N": formula_8, where formula_9. 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 said quantity 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 formula_10 where the number of "arrows" in  each subsequent layer is specified by the value of the next layer below it; that is, formula_11 where formula_12 formula_13 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, formula_14 and  the superscript on "f" indicates an iteration of the function, e.g., formula_15. Expressed in terms of the family of hyperoperations formula_16, the function "f" is the particular sequence formula_17, which is a version of the rapidly growing Ackermann function "A"("n", "n"). (In fact, formula_18 for all "n".) The function "f" can also be expressed in Conway chained arrow notation as formula_19, and this notation also provides the following bounds on "G": formula_20 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 (formula_21) alone: formula_22 where the number of 3s in the expression on the right is formula_23 Now each tetration (formula_24) operation reduces to a power tower (formula_25) according to the definition formula_26 where there are "X" 3s. Thus, formula_27 becomes, solely in terms of repeated "exponentiation towers", formula_28 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, formula_29 (where the number of 3s is formula_30), and then computing the "n" tower in the following sequence: 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 formula_31 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: 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 3formula_323↑…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, . The algorithm above produces the following 500 rightmost decimal digits of Graham's number ():