A Number With No Room to Be Written

Multiplication repeats addition, and a power repeats multiplication. For example, 3 ↑ 3 is another way to write 3³ = 3 × 3 × 3 = 27. Knuth's arrow notation extends this idea by letting another arrow repeat the previous operation.

With two arrows, 3 ↑↑ 3 is a tower of three 3s, evaluated from the top: $3^{(3^3)}=3^{27}=7,625,597,484,987$. With three arrows, 3 ↑↑↑ 3 is a tower whose height is 3 ↑↑ 3, already more than seven trillion levels.

The notation describes these values exactly without expanding all their digits. When an expansion exceeds the laboratory's computation limit, it displays that limit rather than attempting an impractical calculation.

For Graham's number, start with g₁ = 3 ↑↑↑↑ 3, using four arrows. Define each later g by using the previous value as the number of arrows between two 3s. After 64 stages, g₆₄ is Graham's number. It arose as an upper bound in a problem about two-colouring the connections between cube corners.

The decimal expansion is far too large to display, but a remainder calculation can still determine its last digits. The later layers explain why a bound on an expansion is not a bound on everything we can learn about the number.

Try the last digit by hand and the trick appears on its own.

The powers of 3 end in 3, 9, 7, 1, 3, 9, 7, 1, and so on forever: a cycle of four. So to know the last digit of 3 raised to something, you do not need the exponent. You need the exponent's remainder on division by 4, and nothing else at all.

Now take a tower. 3 ↑↑ 2 is 3³ = 27, so its last digit is decided by 3 mod 4, which is 3, giving the third entry of the cycle: 7. Take a taller tower and the exponent changes, but its remainder modulo 4 is all that matters, and that remainder is decided by a shorter version of the same question. The tower has stopped mattering as a size and started mattering only as a remainder.

That is the whole idea. Each storey of the tower only needs to be known modulo something smaller than before, and "something smaller than before" cannot keep shrinking forever. After a bounded number of storeys the question has collapsed to a remainder modulo 1, where every number gives the same answer, and the height has stopped affecting anything.

So a tall enough tower of threes has fixed last digits, and Graham's number is a tower of threes taller than any bound of that kind. The digits are computable not in spite of the number being unimaginable but because of it: the tower is so tall that its exact height became irrelevant.

The catch, and the second view exists to show it, is that the bound grows with how many digits you ask for. One digit needs a tower two storeys tall. Twenty digits need twenty-one. Every extra digit buys another storey, so getting all the digits would need a tower of infinite height, which is precisely the thing that does not exist.

The sentence worth carrying away is this one.

The last digits of Graham's number are computable because the tower is too tall for its height to matter. Nothing else about the number becomes computable along with them.

Everything on this page falls into one of three boxes, and they should not be allowed to blur.

• The last ten digits are 2464195387. Proved, here, by a finite modular argument written out in layer 5 and recomputed twice in the test suite. This is a theorem about Graham's number and it is complete.
• Graham's number has more than $10^{3.6\times 10^{12}}$ digits. This is proved by inequalities between towers. Even an illustrative allowance of $10^{186}$ cells, with one digit per cell, would be insufficient; this comparison is not a physical information-limit theorem.
• The problem Graham's number came from is open. The answer is at least 13, the best known upper bound is now vastly below Graham's number, and where it actually falls is unknown. Nothing on this page searches for it, and computing ten digits contributed nothing to it.

The order matters. A reader who takes the first box as evidence about the third has learned the wrong thing from a page that got everything else right. The digits are a fact about arithmetic modulo 10¹⁰. The problem is a fact about colouring the edges of a hypercube. They share a number and nothing else.

The notation. For $a\ge 1$ and $b\ge 1$ define

Write $3\uparrow \uparrow k$ for the tower of $k$ threes, so $3\uparrow \uparrow 1=3$ and $3\uparrow \uparrow (k+1)=3^{3\uparrow \uparrow k}$.

Graham's number. Set $g_1=3{\uparrow }^{4}3$ and $g_{i+1}=3{\uparrow }^{g_i}3$. Graham's number is $G=g_{64}$.

The Carmichael function. $\lambda (m)$ is the exponent of the group of units modulo $m$: the least $e\ge 1$ with $x^e\equiv 1(\mathrm{mod}m)$ for every $x$ coprime to $m$. On prime powers, $\lambda (2)=1$, $\lambda (4)=2$, $\lambda (2^k)=2^{k-2}$ for $k\ge 3$, and $\lambda (p^k)=p^{k-1}(p-1)$ for odd $p$; on a product of coprime factors it is the least common multiple of theirs.

Generalised Euler. For every integer $x$, every modulus $m\ge 1$ and every exponent $e$,

Both parts of that are conditions, not decoration. The $+\lambda (m)$ may not be dropped, and the hypothesis $e\ge {\log }_{2}m$ may not be dropped.

The claims are then:

1. For each $d\ge 1$ there is a height $H(d)$ such that $3\uparrow \uparrow k\mathrm{mod}10^d$ is the same for every $k\ge H(d)$. Proved in layer 5.
2. $H(d)=d+1$ for $1\le d\le 20$. Exhaustively checked over exactly those twenty values.
3. $G\equiv 2464195387(\mathrm{mod}10^{10})$. Proved, since $G$ is a tower of threes of height far above $H(10)=11$.
4. $G>3\uparrow \uparrow 5$, and $3\uparrow \uparrow 5$ has more than $10^{3.6\times 10^{12}}$ decimal digits, exceeding an illustrative $10^{186}$ storage cells. Proved as arithmetic; the comparison does not establish a physical storage limit.
5. The least $n$ such that every two-colouring of the edges of the $n$-cube contains a single-coloured complete subgraph on four coplanar vertices satisfies $n\ge 13$, and its exact value is open.

Statement 5 is the one the number was invented for, and it is the one this page contributes nothing to.

The stabilisation. Fix $m\ge 1$. Because $\lambda (n)<n$ for every $n>1$, the chain

is strictly decreasing until it reaches 1, so there is a least $J$ with ${\lambda }^J(m)=1$.

Claim: for every $j$ with $0\le j\le J$, the residue $3\uparrow \uparrow k\mathrm{mod}{\lambda }^j(m)$ is the same for all $k\ge (J-j)+3$.

Induct downwards on $j$ from $J$. At $j=J$ the modulus is 1 and every residue is 0, so the statement holds for all $k\ge 3$. Suppose it holds at $j+1$, and take $k,k^{\prime }\ge (J-j)+3$. Then $k-1,k^{\prime }-1\ge (J-j-1)+3$, so by hypothesis

Both of those exponents are at least $3\uparrow \uparrow 3=7,625,597,484,987$, since $k-1\ge 3$, and that comfortably exceeds ${\log }_2{\lambda }^j(m)$ for any modulus a browser will ever hold. So generalised Euler applies to both, with the same reduced exponent, and

Taking $j=0$ gives the claim of layer 4, with $H(d)\le J+3$ where $J$ is the length of the Carmichael chain of $10^d$. $■$

Two remarks about that argument, since both are places it could have gone wrong.

Why the $+\lambda (m)$ cannot be dropped. The sequence $x,x^2,x^3,\dots$ modulo $m$ is eventually periodic with period dividing $\lambda (m)$, but when $x$ shares a factor with $m$ it is not periodic from the start. Take $x=2$ and $m=12$: the powers are $2,4,8,4,8,4,\dots$, so 2 itself never returns. Reducing an exponent to $e\mathrm{mod}\lambda (12)=e\mathrm{mod}2$ could land on $2^1=2$, which the periodic part never visits again, and the answer would be wrong while looking entirely reasonable. Adding $\lambda (m)$ back moves the exponent into the periodic part before the period is used. Three and a power of ten are coprime, so the top of this particular recursion would survive without it, but the chain descends onto moduli where it would not, and an argument that is accidentally correct is not an argument.

Why the hypothesis $e\ge {\log }_{2}m$ cannot be dropped. It is what guarantees the exponent is already past that non-periodic beginning, whose length is below ${\log }_{2}m$ for every $x$. Here the smallest exponent the step is ever applied to is $3\uparrow \uparrow 3$, thirteen digits long, and the largest modulus is $10^{20}$, whose logarithm base two is under 67. The kernel checks this inequality rather than assuming it.

The digits. With $m=10^{10}$ the Carmichael chain has twelve links, so residues are constant from height 15 upwards, and a direct check finds them constant from height 11. Graham's number is $g_{64}$, a tower of threes whose height is not writable and is certainly above 11. Computing $3\uparrow \uparrow 11\mathrm{mod}10^{10}$ by the recursion gives 2464195387. $■$

The size. $G=g_{64}>g_1=3{\uparrow }^{4}3>3{\uparrow }^{3}3$. The last expression is a tower of threes of height $3\uparrow \uparrow 3$, far above 5. To bound the digit count explicitly, write $T_4=3^{7625597484987}$ for a tower of four threes. Since $3^{40}>10^{19}$, we have ${\log }_{10}(3)>19/40=0.475$, and hence $T_4>10^{3.61\times 10^{12}}$. For a tower of five threes,

Its decimal digit count, $\lfloor {\log }_{10}(3^{T_4})\rfloor +1$, is therefore larger still. That exceeds $10^{186}$. $■$

For scale, assuming a spherical radius of $4.4\times 10^{26}$ metres and a Planck length of $1.616255\times 10^{-35}$ metres gives $(4\pi /3)(r/{\ell }_P{)}^3\approx 8.45\times 10^{184}$ Planck volumes, below that illustrative allowance. The Planck length comes from CODATA; the radius is an assumption for the comparison. Neither assumption makes these volumes actual memory cells.

What is not proved here. Anything about the Ramsey problem. Any digit of $G$ other than the last ten, including the first. The value of $H(d)$ for $d>20$, which is checked over a finite range and not derived.

What this laboratory computes. Up-arrow expressions exactly while the answer has at most a hundred thousand decimal digits, which in practice means 3 ↑ 3 and 3 ↑↑ 3 and nothing else; and the last one to twenty digits of a tower of threes, exactly, modulo the appropriate power of ten. Both are exact integer arithmetic with no approximation anywhere. The refusal at the third rung is a refusal, not a timeout: the size is estimated from logarithms before any work begins, and the work is never started.

Twenty digits, and why not more. Nothing about the method breaks at twenty. The Carmichael chain of 10¹⁰⁰ is still short, and a hundred digits would compute in the same instant. Twenty is where the figure stops being readable, which is a decision about the drawing rather than about the mathematics. What does break, and breaks immediately, is asking for all of them: the required tower height grows with the number of digits, and Graham's number has no finite decimal expansion within reach of any height a description could name.

The problem is still open. Graham's number entered mathematics as an upper bound for a question about colouring the edges of a hypercube, and that question has not been answered. The lower bound is 13. The best known upper bound is now enormously smaller than Graham's number itself, which means the famous number is no longer even the state of the art in the one role it was invented for. A reader who arrives believing the number is important because it is large should leave knowing that it is remembered because it was a bound, and that the bound has been beaten.

A caution about the attribution. The number now called Graham's number does not appear in Graham and Rothschild's 1971 paper. The bound published there is smaller and harder to state; the famous one was described by Graham to Martin Gardner and printed in 1977. Both are in the sources below, with bibliographic review notes distinguishing the original text from the publisher's record.

Read this next to the Collatz orbit atlas. There a browser can compute astonishingly far and settle nothing, because the question is about every number. Here a browser can compute almost nothing and settles a question exactly, because the question was narrowed to ten digits. The lesson is the same in both directions: what closes a question is the argument available, never the size of the computation.