# Graham's number

Talk30*3,155*pages on

this wiki

*For other uses, see Graham's number (disambiguation).*

**Graham's number** is a famous large number, defined by Ronald Graham.^{[1]}

Using up-arrow notation, it is defined as:

\begin{eqnarray*} g_0 &=& 4 \\ g_1 &=& 3 \uparrow\uparrow\uparrow\uparrow 3 \\ g_2 &=& 3 \underbrace{\uparrow\uparrow\cdots\uparrow\uparrow}_{g_1 \text{ arrows}} 3 \\ g_{k + 1} &=& 3 \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow\uparrow\uparrow}_{g_k \text{ arrows}} 3 \\ g_{64} &=& \text{Graham's number} \end{eqnarray*}

Graham's number is celebrated as the largest number ever used in a mathematical proof, although much larger numbers have since claimed this title (such as TREE(3) and SCG(13)). The smallest Bowersism exceeding Graham's number is corporal.

## History Edit

Graham's number arose out of the following unsolved problem in Ramsey Theory:

LetN*be the smallest dimensionnof a hypercube such that if the lines joining all pairs of corners are two-colored for anyn≥N*, a complete graph K_{4}of one color with coplanar vertices will be forced. FindN*.

Graham published a paper proving that the answer exists, providing the upper bound \(F^{7}(12)\), where \(F(n) = 2 \uparrow^{n} 3\) in arrow notation.^{[2]} Sbiis Saibian calls this number "Little Graham". Graham's number appeared in an earlier unpublished paper, made famous when Martin Gardner wrote about it in *Scientific American*. In 2013, the upper bound was further reduced to *N'* = 2↑↑2↑↑2↑↑9 using the Hales–Jewett theorem.^{[3]} As of 2014, the best known *lower* bound for *N** is 13.

Gardner's article contained a minor error, where he claimed that 3↑↑7625597484987 = 3↑(7625597484987↑7625597484987); it is actually 3↑(3↑↑7625597484986).

## Comparison Edit

Since g_{0} is 4 and not 3, Graham's number cannot be expressed efficiently with most major googological functions. It can be approximated with \(3 → 3 → 64 → 2\) in Conway's Chained Arrow Notation or \(\{ 3,65,1,2\}\) in BEAF, with upper bound \(\{3, 66, 1, 2\}\). A rare example of an exact representation is Jonathan Bowers' G functions, where it is.G^{64}4 in base 3.

Tim Chow proved that Graham's number is much larger than the Moser.^{[4]} The proof hinges on the fact that, using Steinhaus-Moser Notation, *n* in a (*k* + 2)-gon is less than \(n\underbrace{\uparrow\uparrow\ldots\uparrow\uparrow}_{2k-1}n\). He sent the proof to Susan Stepney on July 7, 1998.^{[5]} Coincidentally, Stepney was sent a similar proof by Todd Cesere several days later.

It has been proven that Graham's number is much less than \(\Sigma(64)\),^{[6]} and later a better upper bound \(\Sigma(23)\) was proven.

## Calculating last digits Edit

The final digits of Graham's number can be computed by taking advantage of the convergence of last digits, because Graham's number is a power tower of threes. Here is a simple algorithm to obtain the last \(x\) digits \(N(x)\) of Graham's number:

- \(N(0) = 3\)
- \(N(x) = 3^{N(x-1)} \text{ mod } 10^x\)

For example:

- \(N(1) = 3^{N(0)} \equiv 3^3 \equiv 27 \equiv 7 \pmod{10}\), so the last digit is 7.
- \(N(2) = 3^{N(1)} \equiv 3^7 \equiv 2187 \equiv 87 \pmod{100}\), so the last two digits are 87.
- \(N(3) = 3^{N(2)} \equiv 3^{87} \equiv 323257909929174534292273980721360271853387 \equiv 387 \pmod{1000}\), so the last three digits are 387.
- etc.

This naive method is not very efficient, since number of digits in the leftmost expression grows exponentially. We can use right-to left binary method instead:

- Convert the exponent into binary form. E.g. \(87_{10} = 1010111_2\)
- If last digit of exponent is 1, then multiply base to result and square base.
- Otherwise, just square base.

Using this, it can be shown that last 20 digits of Graham's number are: \(...04575627262464195387\).^{[7]}

## Video Edit

Source: Graham's Number - Numberphile

## Sources Edit

- ↑ Graham's Number
- ↑ Graham & Rothchild 1971 paper
- ↑ http://arxiv.org/pdf/1304.6910v1.pdf
- ↑ Proof that
*G*>>*M*. (This website uses*n*[*m*] =*n*inside an*m*-gon for Steinhaus-Moser Notation.) - ↑ Stepney, Susan. Moser's polygon notation. Retrieved 2013-03-17.
- ↑ Proof that BB(64) >> G
- ↑ Last 10000 digits of G

## See also Edit

- Moser
- Little Graham
- Folkman's number
- Expansion
- Grahal, a number equal to \(g_1\)

**By Harvey Friedman:** Mythical tree problem · Friedman's vector reduction problem · Friedman's finite ordered tree problem · block subsequence theorem n(4) · Friedman's circle theorem · TREE sequence TREE(3) · subcubic graph number SCG(13) · Friedman's finite games**Hydras:** Kirby-Paris · Buchholz · Aarex · Array · Extended Array · Ex-Extended Array**Miscellaneous:** Exploding Tree Function · **Graham's number** · fusible number · Goodstein function · Laver table