Graham's number
   HOME

TheInfoList



OR:

Graham's number is an immense number that arose as an
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
on the answer of a problem in the mathematical field of
Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
. It is much larger than many other large numbers such as
Skewes's number In number theory, Skewes's number is any of several large numbers used by the South African mathematician Stanley Skewes as upper bounds for the smallest natural number x for which :\pi(x) > \operatorname(x), where is the prime-counting function ...
and Moser's number, both of which are in turn much larger than a
googolplex A googolplex is the number 10, or equivalently, 10 or 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 . Written out in ordinary decimal notation, it is 1 fol ...
. As with these, it is so large that the
observable universe The observable universe is a ball-shaped region of the universe comprising all matter that can be observed from Earth or its space-based telescopes and exploratory probes at the present time, because the electromagnetic radiation from these obj ...
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 a ^. However, Graham's number can be explicitly given by
computable Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
formulas using
Knuth's up-arrow notation In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976. In his 1947 paper, R. L. Goodstein introduced the specific sequence of operations that are now called ''hyperoperati ...
or equivalent, as was done by
Ronald Graham Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...
, the number's namesake. 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 via simple algorithms; the last 13 digits are ...7262464195387. With Knuth's up-arrow notation, Graham's number is g_, where g_n = \left\ \text where the number of ''arrows'' in each subsequent layer is specified by the value of the next layer below it; that is, G = g_, where g_1=3\uparrow\uparrow\uparrow\uparrow 3, g_n = 3\uparrow^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''1 with four up-arrows between 3s; the second step is to calculate ''g''2 with ''g''1 up-arrows between 3s; the third step is to calculate ''g''3 with ''g''2 up-arrows between 3s; and so on, until finally calculating ''G'' = ''g''64 with ''g''63 up-arrows between 3s. Equivalently, G = f^(4),\textf(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)))). Expressed in terms of the family of
hyperoperation In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called ''hyperoperations'' in this context) that starts with a unary operation (the successor function with ''n'' = 0). The sequence continues with ...
s \text_0, \text_1, \text_2, \cdots, the function ''f'' is the particular sequence f(n) = \text_(3,3), which is a version of the rapidly growing Ackermann function ''A''(''n'', ''n''). (In fact, f(n) > A(n, n) for all ''n''.) The function ''f'' can also be expressed in
Conway chained arrow notation Conway chained arrow notation, created by mathematician John Horton Conway, is a means of expressing certain extremely large numbers. It is simply a finite sequence of positive integers separated by rightward arrows, e.g. 2\to3\to4\to5\to6. As wit ...
as f(n) = 3 \rightarrow 3 \rightarrow n, and this notation also provides the following bounds on ''G'': 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''1) of the rapidly growing 64-term sequence. First, in terms of
tetration In mathematics, tetration (or hyper-4) is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though \uparrow \uparrow and the left-exponent ''xb'' are common. Under the definition as rep ...
( \uparrow\uparrow) alone: 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 \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow (3 \uparrow \uparrow 3). Now each tetration (\uparrow\uparrow) operation reduces to a power tower (\uparrow) according to the definition 3 \uparrow\uparrow X = 3 \uparrow (3 \uparrow (3 \uparrow \dots (3 \uparrow 3) \dots )) = 3^ where there are ''X'' 3s. Thus, g_1 = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots )) \quad \text \quad 3 \uparrow \uparrow (3 \uparrow \uparrow 3) becomes, solely in terms of repeated "exponentiation towers", g_1 = \left. \begin3^\end \right \} \left. \begin3^\end \right \} \dots \left. \begin3^\end \right \} 3 \quad \text \quad \left. \begin3^\end \right \} \left. \begin3^\end \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''1 is computed by first calculating the number of towers, n = 3\uparrow (3\uparrow (3\ \dots\ \uparrow 3)) (where the number of 3s is 3\uparrow (3\uparrow 3) = 7625597484987), and then computing the ''n''th 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''1 = ''n''th tower: 3↑3↑3↑3↑3↑3↑3↑...↑3 (number of 3s is given by the ''n-1''th 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''1. The magnitude of this first term, ''g''1, 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''1, is far greater than the number of Planck volumes (roughly 10185 of them) into which one can imagine subdividing the
observable universe The observable universe is a ball-shaped region of the universe comprising all matter that can be observed from Earth or its space-based telescopes and exploratory probes at the present time, because the electromagnetic radiation from these obj ...
. And after this first term, still another 63 terms remain in the rapidly growing ''g'' sequence before Graham's number ''G'' = ''g''64 is reached. To illustrate just how fast this sequence grows, while ''g''1 is equal to 3 \uparrow \uparrow \uparrow \uparrow 3 with only four up arrows, the number of up arrows in ''g''2 is this incomprehensibly large number ''g''1.


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 In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...
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''d'' 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 3\scriptstyle\uparrow3↑…3↑''x'' mod 10''d'', 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 Assignment, assign or The Assignment may refer to: * Homework * Sex assignment * The process of sending National Basketball Association players to its development league; see Computing * Assignment (computer science), a type of modification to ...
''x'' = 3''x'' mod 10''d''. 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''k'')≡ Gmod 10''k''). ''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 (): ...02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780 38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387


References


Bibliography

* ; reprinted (revised) in Gardner (2001), cited below. * * * The explicit formula for ''N'' appears on p. 290. This is not the "Graham's number" ''G'' published by Martin Gardner. * 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
*

by Geoff Exoo






Some Ramsey results for the n-cube
prepublication mentions Graham's number * * Archived a
Ghostarchive
and th
Wayback Machine
* Archived a
Ghostarchive
and th
Wayback Machine

The last 16 million digits of Graham's number
by the Darkside communication group {{DEFAULTSORT:Graham's Number Ramsey theory Integers Large integers