View source for Knuth's up-arrow notation

{{short description|Method of notation of very large integers}}

In [[mathematics]], '''Knuth's up-arrow notation''' is a method of notation for [[Large number|very large]] [[Integer|integers]], introduced by [[Donald Knuth]] in 1976.<ref>{{cite journal | last =Knuth | first = Donald E.| year=1976|title=Mathematics and Computer Science: Coping with Finiteness |journal=Science | volume=194|issue=4271| pages=1235–1242 | doi=10.1126/science.194.4271.1235 | pmid=17797067 |bibcode=1976Sci...194.1235K| s2cid = 1690489}}</ref>

In his 1947 paper,<ref>{{cite journal
  | author= R. L. Goodstein
  | title= Transfinite Ordinals in Recursive Number Theory
  | journal= Journal of Symbolic Logic
  |date=Dec 1947
  | volume= 12
  | issue= 4
  | pages= 123–129
  | doi= 10.2307/2266486
  | jstor= 2266486| s2cid= 1318943
 }}</ref> [[R. L. Goodstein]] introduced the specific sequence of operations that are now called [[Hyperoperation|''hyperoperations'']]. Goodstein also suggested the Greek names [[tetration]], [[pentation]], etc., for the extended operations beyond [[exponentiation]]. The sequence starts with a [[unary operation]] (the [[successor function]] with ''n'' = 0), and continues with the [[binary operation]]s of [[addition]] (''n'' = 1), [[multiplication]] (''n'' = 2), [[exponentiation]] (''n'' = 3), [[tetration]] (''n'' = 4), [[pentation]] (''n'' = 5), etc.
[[Hyperoperation#Notations|Various notations]] have been used to represent hyperoperations. One such notation is <math>H_n(a,b)</math>.
Knuth's up-arrow notation <math>\uparrow</math> is another. 
For example:
* the single arrow <math>\uparrow</math> represents [[exponentiation]] (iterated multiplication) <math display="block">2 \uparrow 4 = H_3(2,4) = 2\times(2\times(2\times 2)) = 2^4 = 16</math>
* the double arrow <math>\uparrow\uparrow</math> represents [[tetration]] (iterated exponentiation) <math display="block"> 2 \uparrow\uparrow 4 = H_4(2,4) = 2 \uparrow (2 \uparrow (2 \uparrow 2))= 2^{2^{2^{2}}} = 2^{16} = 65,536</math>
* the triple arrow <math>\uparrow\uparrow\uparrow</math> represents [[pentation]] (iterated tetration) <math display="block">\begin{align}
2 \uparrow\uparrow\uparrow 4 = H_5(2,4) = 2 \uparrow\uparrow (2 \uparrow\uparrow (2 \uparrow\uparrow 2 ))\\ 
&= 2 \uparrow\uparrow (2 \uparrow\uparrow (2 \uparrow 2 ))\\
&= 2 \uparrow\uparrow (2 \uparrow\uparrow 4 )\\
&= \underbrace{2 \uparrow (2 \uparrow (2 \uparrow\dots ))}
  \; = \; \underbrace{ \; 2^{2^{\cdots^2}}}\\
& \;\;\;\;\; 2 \uparrow\uparrow 4 \mbox{ copies of } 2
  \;\;\;\;\; \mbox{65,536 2s}\\
\end{align}</math>
The general definition of the up-arrow notation is as follows (for <math>a \ge 0, n \ge 1, b \ge 0</math>):
<math display="block">a\uparrow^nb = H_{n+2}(a,b) = a[n+2]b.</math>
Here, <math>\uparrow^n</math> stands for ''n'' arrows, so for example
<math display="block">2 \uparrow\uparrow\uparrow\uparrow 3 = 2\uparrow^4 3.</math>
The square brackets are another notation  for hyperoperations.

==Introduction==
The [[hyperoperations]] naturally extend the [[arithmetic]] operations of [[addition]] and [[multiplication]] as follows.
[[Addition]] by a [[natural number]] is defined as iterated incrementation:
:<math>
  \begin{matrix}
   H_1(a,b) = a+b = & a+\underbrace{1+1+\dots+1} \\
   & b\mbox{ copies of }1
  \end{matrix} 
 </math>
   
[[Multiplication]] by a [[natural number]] is defined as iterated [[addition]]:
:<math>
  \begin{matrix}
   H_2(a,b) = a\times b = & \underbrace{a+a+\dots+a} \\
   & b\mbox{ copies of }a
  \end{matrix} 
 </math>

For example,

:<math>
  \begin{matrix}
   4\times 3 & = & \underbrace{4+4+4} & = & 12\\
   & & 3\mbox{ copies of }4
  \end{matrix} 
 </math>

[[Exponentiation]] for a natural power <math>b</math> is defined as iterated multiplication, which Knuth denoted by a single up-arrow:

:<math>
  \begin{matrix}
   a\uparrow b = H_3(a,b) = a^b = & \underbrace{a\times a\times\dots\times a}\\
   & b\mbox{ copies of }a
  \end{matrix} 
 </math>

For example,

:<math>
  \begin{matrix}
   4\uparrow 3= 4^3 = & \underbrace{4\times 4\times 4} & = & 64\\
   & 3\mbox{ copies of }4
  \end{matrix} 
 </math>

[[Tetration]] is defined as iterated exponentiation, which Knuth denoted by a “double arrow”:
:<math>
  \begin{matrix}
   a\uparrow\uparrow b = H_4(a,b) = &  \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} & 
   = & \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))} 
\\  
    & b\mbox{ copies of }a
    & & b\mbox{ copies of }a
  \end{matrix}
 </math>

For example,

:<math>
  \begin{matrix}
   4\uparrow\uparrow 3 = & \underbrace{4^{4^4}} & 
   = & \underbrace{4\uparrow (4\uparrow 4)} & = & 4^{256} & \approx & 1.34078079\times 10^{154}&
\\  
    & 3\mbox{ copies of }4
    & &3\mbox{ copies of }4
  \end{matrix} 
 </math>

Expressions are evaluated from right to left, as the operators are defined to be [[Right associative operator|right-associative]].

According to this definition,
:<math>3\uparrow\uparrow 2=3^3=27 </math>
:<math>3\uparrow\uparrow 3=3^{3^3}=3^{27}=7,625,597,484,987 </math>
:<math>3\uparrow\uparrow 4=3^{3^{3^3}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}
 </math> 
:<math>3\uparrow\uparrow 5=3^{3^{3^{3^3}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}\approx 3^{1.2580143\times 10^{3638334640024}} </math>
:etc.

This already leads to some fairly large numbers, but the hyperoperator sequence does not stop here.

[[Pentation]], defined as iterated tetration, is represented by the “triple arrow”:
:<math>
  \begin{matrix}
   a\uparrow\uparrow\uparrow b = H_5(a,b) = &
    \underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}\\
    & b\mbox{ copies of }a
  \end{matrix}
 </math>
[[Hexation]], defined as iterated pentation, is represented by the “quadruple arrow”:
:<math>
  \begin{matrix}
   a\uparrow\uparrow\uparrow\uparrow b = H_6(a,b) = &
    \underbrace{a_{}\uparrow\uparrow\uparrow (a\uparrow\uparrow\uparrow(\dots\uparrow\uparrow\uparrow a))}\\
    & b\mbox{ copies of }a
  \end{matrix}
 </math>

and so on. The general rule is that an <math>n</math>-arrow operator expands into a right-associative series of (<math>n - 1</math>)-arrow operators. Symbolically,
:<math>
  \begin{matrix}
   a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}_{n}\ b=
    \underbrace{a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow}_{n-1}
    \ (a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}_{n-1}
    \ (\dots
    \ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}_{n-1}
    \ a))}_{b\text{ copies of }a}
  \end{matrix}
 </math>

Examples:

:<math>3\uparrow\uparrow\uparrow2 = 3\uparrow\uparrow3 = 3^{3^3} = 3^{27}=7,625,597,484,987</math>

:<math>
  \begin{matrix}
    3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow\uparrow3) = 3\uparrow\uparrow(3\uparrow3\uparrow3) = &
    \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\
   & 3\uparrow3\uparrow3\mbox{ copies of }3
  \end{matrix}
  \begin{matrix}
   = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\
   & \mbox{7,625,597,484,987 copies of 3}
  \end{matrix}
  \begin{matrix}
   = & \underbrace{3^{3^{3^{3^{\cdot^{\cdot^{\cdot^{\cdot^{3}}}}}}}}} \\
   & \mbox{7,625,597,484,987 copies of 3}
  \end{matrix}
 </math>

==Notation==
In expressions such as <math>a^b</math>, the notation for exponentiation is usually to write the exponent <math>b</math> as a superscript to the base number <math>a</math>. But many environments &mdash; such as [[programming language]]s and plain-text [[e-mail]] &mdash; do not support [[superscript]] typesetting. People have adopted the linear notation <math>a \uparrow b</math> for such environments; the up-arrow suggests 'raising to the power of'. If the [[character set]] does not contain an up arrow, the [[caret]] (^) is used instead.

The superscript notation <math>a^b</math> doesn't lend itself well to generalization, which explains why Knuth chose to work from the inline notation <math>a \uparrow b</math> instead.

<math>a \uparrow^n b</math> is a shorter alternative notation for n uparrows. Thus <math>a \uparrow^4 b = a \uparrow \uparrow \uparrow \uparrow b</math>.

===Writing out up-arrow notation in terms of powers===
Attempting to write <math>a \uparrow \uparrow b</math> using the familiar superscript notation gives a [[tetration|power tower]].

:For example: <math>a \uparrow \uparrow 4 = a \uparrow (a \uparrow (a \uparrow a)) = a^{a^{a^a}}</math>

If <math>b</math> is a variable (or is too large), the power tower might be written using dots and a note indicating the height of the tower.

:<math>a \uparrow \uparrow b = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}</math>

Continuing with this notation, <math>a \uparrow \uparrow \uparrow b</math> could be written with a stack of such power towers, each describing the size of the one above it.

:<math>a \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow (a \uparrow \uparrow (a \uparrow \uparrow a)) = 
  \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{a} }}</math>

Again, if <math>b</math> is a variable or is too large, the stack might be written using dots and a note indicating its height.

:<math>a \uparrow \uparrow \uparrow b = 
  \left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} b</math>

Furthermore, <math>a \uparrow \uparrow \uparrow \uparrow b</math> might be written using several columns of such stacks of power towers, each column describing the number of power towers in the stack to its left:

:<math>a \uparrow \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow a)) = 
  \left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                     \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                     \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                     a</math>

And more generally:

:<math>a \uparrow \uparrow \uparrow \uparrow b = 
  \underbrace{
    \left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                       \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                       \cdots \right\}
                       a
  }_{b}</math>

This might be carried out indefinitely to represent <math>a \uparrow^n b</math> as iterated exponentiation of iterated exponentiation for any <math>a</math>, <math>n</math>, and <math>b</math> (although it clearly becomes rather cumbersome).

====Using tetration====

The Rudy Rucker notation <math>^{b}a</math> for [[tetration]] allows us to make these diagrams slightly simpler while still employing a geometric representation (we could call these ''tetration towers'').

: <math> a \uparrow \uparrow b = { }^{b}a</math>

: <math> a \uparrow \uparrow \uparrow b = \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{b}</math>

: <math> a \uparrow \uparrow \uparrow \uparrow b = 
   \left. \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{\vdots}_{a} }} \right\} b</math>

Finally, as an example, the fourth Ackermann number <math>4 \uparrow^4 4</math> could be represented as:
: <math>\underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{4} }} = 
        \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ ^{^{^{4}4}4}4 }}</math>

==Generalizations==
Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an ''n''-arrow operator  <math>\uparrow^n</math> is useful (and also for descriptions with a variable number of arrows), or equivalently, [[hyper operator]]s.

Some numbers are so large that even that notation is not sufficient. The [[Conway chained arrow notation]] can then be used: a chain of three elements is equivalent with the other notations, but a chain of four or more is even more powerful.

:<math>
  \begin{matrix}
   a\uparrow^n b & = & a [n+2] b & = & a\to b\to n \\
   \mbox{(Knuth)} & & \mbox{(hyperoperation)} & & \mbox{(Conway)}
  \end{matrix}
 </math>
<math>6\uparrow\uparrow4</math> = <math>\underbrace{6^{6^{.^{.^{.^{6}}}}}}_{4}</math>, Since <math>6\uparrow\uparrow4</math> = <math>6^{6^{6^{6}}}</math> = <math>6^{6^{46,656}}</math>, Thus the result comes out with <math>\underbrace{6^{6^{.^{.^{.^{6}}}}}}_{4}</math>

<math>10\uparrow(3\times10\uparrow(3\times10\uparrow15)+3)</math> = <math>\underbrace{100000...000}_{ \underbrace{300000...003}_{\underbrace{300000...000}_{15} }}</math> or <math>10^{3\times10^{3\times10^{15}}+3}</math> (Petillion)

Even faster-growing functions can be categorized using an [[ordinal number|ordinal]] analysis called the [[fast-growing hierarchy]]. The fast-growing hierarchy uses successive function iteration and diagonalization to systematically create faster-growing functions from some base function <math>f(x)</math>. For the standard fast-growing hierarchy using <math>f_0(x) = x+1</math>, <math>f_2(x)</math> already exhibits exponential growth, <math>f_3(x)</math> is comparable to tetrational growth and is upper-bounded by a function involving the first four hyperoperators;. Then, <math>f_\omega(x)</math> is comparable to the [[Ackermann function]], <math>f_{\omega + 1}(x)</math> is already beyond the reach of indexed arrows but can be used to approximate [[Graham's number]], and <math>f_{\omega^2}(x)</math> is comparable to arbitrarily-long Conway chained arrow notation.

These functions are all computable. Even faster computable functions, such as the [[Goodstein sequence]] and the [[TREE(3)|TREE sequence]] require the usage of large ordinals, may occur in certain combinatorical and proof-theoretic contexts. There exist functions which grow uncomputably fast, such as the [[Busy Beaver]], whose very nature will be completely out of reach from any up-arrow, or even any ordinal-based analysis.

==Definition==

Without reference to [[hyperoperation]] the up-arrow operators can be formally defined by

:<math>
  a\uparrow^n b=
   \begin{cases}
    a^b, & \text{if }n=1; \\
    1, & \text{if }n>1\text{ and }b=0; \\
    a\uparrow^{n-1}(a\uparrow^{n}(b-1)), & \text{otherwise }
   \end{cases}
 </math>
for all integers <math>a, b, n</math> with <math>a \ge 0, n \ge 1, b \ge 0</math><ref group="nb" name=corona2/>.

This definition uses [[exponentiation]] <math>(a\uparrow^1 b = a\uparrow b = a^b)</math> as the base case, and [[tetration]] <math>(a\uparrow^2 b = a\uparrow\uparrow b)</math> as repeated exponentiation.  This is equivalent to the [[Hyperoperation#Definition|hyperoperation sequence]] except it omits the three more basic operations of [[Successor_function|succession]], [[addition]] and [[multiplication]].

One can alternatively choose [[multiplication]] <math>(a\uparrow^0 b = a \times b)</math> as the base case and iterate from there. Then [[exponentiation]] becomes repeated multiplication. The formal definition would be
:<math>
  a\uparrow^n b=
   \begin{cases}
    a\times b, & \text{if }n=0; \\
    1, & \text{if }n>0\text{ and }b=0; \\
    a\uparrow^{n-1}(a\uparrow^{n}(b-1)), & \text{otherwise }
   \end{cases}
 </math>
for all integers <math>a, b, n</math> with <math>a \ge 0, n \ge 0, b \ge 0</math>.

Note, however, that Knuth did not define the "nil-arrow" (<math>\uparrow^0</math>). One could extend the notation to negative indices (n ≥ -2) in such a way as to agree with the entire hyperoperation sequence, except for the lag in the indexing:
:<math>H_n(a, b) = a [n] b = a \uparrow^{n-2}b\text{ for } n \ge 0.</math>

The up-arrow operation is a [[Associative property#Notation for non-associative operations|right-associative operation]], that is, <math>a \uparrow b \uparrow c</math> is understood to be <math>a \uparrow (b \uparrow c)</math>, instead of <math>(a \uparrow b) \uparrow c</math>. If ambiguity is not an issue parentheses are sometimes dropped.

==Tables of values==
<!-- This section is linked from [[Hyper operator]] -->

===Computing 0↑<sup>''n''</sup>&nbsp;''b''===

Computing <math>0\uparrow^n b = H_{n+2}(0,b) = 0[n+2]b</math> results in
:0, when ''n'' = 0&nbsp; <ref group="nb" name="corona1">Keep in mind that Knuth did not define the operator <math>\uparrow^0</math>.</ref>
:1, when ''n'' = 1 and ''b'' = 0 &nbsp; <ref group="nb" name=corona2>For more details, see [[Exponentiation#Powers of zero|Powers of zero]].</ref><ref group="nb" name=corona3>For more details, see [[Zero to the power of zero]].</ref>
:0, when ''n'' = 1 and ''b'' > 0 &nbsp; <ref group="nb" name=corona2/><ref group="nb" name=corona3/>
:1, when ''n'' > 1 and ''b'' is even (including 0)
:0, when ''n'' > 1 and ''b'' is odd

===Computing 2↑<sup>''n''</sup>&nbsp;''b''===

Computing <math>2\uparrow^n b</math> can be restated in terms of an infinite table. We place the numbers <math>2^b</math> in the top row, and fill the left column with values 2. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

{| class="wikitable"
|+ Values of <math>2\uparrow^n b</math> = [[Hyperoperation#Notations|<math>H_{n+2}(2,b)</math>]] = [[Hyperoperation#Notations|<math>2[n+2]b</math>]] = [[Conway chained arrow notation|2 → b → n]]
|-
! {{diagonal split header|''ⁿ''|''b''}}
! 1
! 2
! 3
! 4
! 5
! 6
! formula
|-
! 1
| 2 || 4 || 8 || 16 || 32 || 64 || <math>2^b</math>
|-
! 2
| 2 || 4 || 16 || 65536 || <math>2^{65{,}536}\approx 2.0 \times 10^{19{,}728}</math> || <math>2^{2^{65{,}536}}\approx 10^{6.0 \times 10^{19{,}727}}</math> || <math>2\uparrow\uparrow b</math>
|-
! 3
| 2 || 4 || 65536 || <math>
  \begin{matrix}
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}} \\
   65{,}536\mbox{ copies of }2  \end{matrix}
</math> || <math>
  \begin{matrix}
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}\\
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}\\
   65{,}536\mbox{ copies of }2
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}\\
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}\\
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}\\
   65{,}536\mbox{ copies of }2
  \end{matrix}</math> || <math>2\uparrow\uparrow\uparrow b</math> 
|-
! 4
| 2 || 4 || <math>
  \begin{matrix}
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}}\\
   65{,}536\mbox{ copies of }2
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{2}.}.}.}2}2}\\
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}\\
   65{,}536\mbox{ copies of }2
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{2}.}.}.}2}2}\\
   \underbrace{^{^{^{^{^{2}.}.}.}2}2}\\
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}\\
   65{,}536\mbox{ copies of }2
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{2}.}.}.}2}2}\\
   \underbrace{^{^{^{^{^{2}.}.}.}2}2}\\
   \underbrace{^{^{^{^{^{2}.}.}.}2}2}\\
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}\\
   65{,}536\mbox{ copies of }2
  \end{matrix}</math>
| <math>2\uparrow\uparrow\uparrow\uparrow b</math>
|}

The table is the same as [[Ackermann function#Table of values|that of the Ackermann function]], except for a shift in <math>n</math> and <math>b</math>, and an addition of 3 to all values.

===Computing 3↑<sup>''n''</sup>&nbsp;''b''===

We place the numbers <math>3^b</math> in the top row, and fill the left column with values 3. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

{| class="wikitable"
|+ Values of <math>3\uparrow^n b</math> = [[Hyperoperation#Notations|<math>H_{n+2}(3,b)</math>]] = [[Hyperoperation#Notations|<math>3[n+2]b</math>]] = [[Conway chained arrow notation|3 → b → n]]
|-
! {{diagonal split header|''ⁿ''|''b''}}
! 1
! 2
! 3
! 4
! 5
! formula
|-
! 1
| 3 || 9 || 27 || 81 || 243 || <math>3^b</math>
|-
! 2
| 3 || 27 || 7,625,597,484,987  || <math>3^{7{,}625{,}597{,}484{,}987}\approx 1.3 \times 10^{3{,}638{,}334{,}640{,}024}</math>  ||  <math>3^{3^{7{,}625{,}597{,}484{,}987}}</math> || <math>3\uparrow\uparrow b</math>
|-
! 3
| 3 || 7,625,597,484,987 || <math>
  \begin{matrix}
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
   7{,}625{,}597{,}484{,}987\mbox{ copies of }3
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}}\\
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}}\\
   7{,}625{,}597{,}484{,}987\mbox{ copies of }3
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}}\\
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}}\\
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}}\\
   7{,}625{,}597{,}484{,}987\mbox{ copies of }3
  \end{matrix}</math> || <math>3\uparrow\uparrow\uparrow b</math>
|-
! 4
| 3 || <math>\begin{matrix}
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
   7{,}625{,}597{,}484{,}987\mbox{ copies of }3
  \end{matrix}</math> || <math>\begin{matrix}
   \underbrace{^{^{^{^{^{3}.}.}.}3}3}\\
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
   7{,}625{,}597{,}484{,}987\mbox{ copies of }3
  \end{matrix}</math> || <math>\begin{matrix}
   \underbrace{^{^{^{^{^{3}.}.}.}3}3}\\
   \underbrace{^{^{^{^{^{3}.}.}.}3}3}\\
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
   7{,}625{,}597{,}484{,}987\mbox{ copies of }3
  \end{matrix}</math> || <math>\begin{matrix}
   \underbrace{^{^{^{^{^{3}.}.}.}3}3}\\
   \underbrace{^{^{^{^{^{3}.}.}.}3}3}\\
   \underbrace{^{^{^{^{^{3}.}.}.}3}3}\\
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
   7{,}625{,}597{,}484{,}987\mbox{ copies of }3
  \end{matrix}</math>
| <math>3\uparrow\uparrow\uparrow\uparrow b</math>
|}

===Computing 4↑<sup>''n''</sup>&nbsp;''b''===

We place the numbers <math>4^b</math> in the top row, and fill the left column with values 4. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

{| class="wikitable"
|+ Values of <math>4\uparrow^n b</math> = [[Hyperoperation#Notations|<math>H_{n+2}(4,b)</math>]] = [[Hyperoperation#Notations|<math>4[n+2]b</math>]] = [[Conway chained arrow notation|4 → b → n]]
|-
! {{diagonal split header|''ⁿ''|''b''}}
! 1
! 2
! 3
! 4
! 5
! formula
|-
! 1
| 4 || 16 || 64 || 256 || 1024 || <math>4^b</math>
|-
! 2
| 4 || 256 || <math>4^{256}\approx 1.34 \times 10^{154}</math>  || <math>4^{4^{256}}\approx 10^{8.0 \times 10^{153}}</math>  ||  <math>4^{4^{4^{256}}}</math> || <math>4\uparrow\uparrow b</math>
|-
! 3
| 4 || <math>4^{4^{256}}\approx 10^{8.0 \times 10^{153}}</math> || <math>
  \begin{matrix}
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^4}}}}}}\\
   4^{4^{256}}\mbox{ copies of }4
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^4}}}}}}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^4}}}}}}\\
   4^{4^{256}}\mbox{ copies of }4
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^4}}}}}}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^4}}}}}}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^4}}}}}}\\
   4^{4^{256}}\mbox{ copies of }4
  \end{matrix}</math> || <math>4\uparrow\uparrow\uparrow b</math>
|-
! 4
| 4 || <math>
  \begin{matrix}
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}}\\
   4^{4^{256}}\mbox{ copies of }4
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{4}.}.}.}4}4}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}}\\
   4^{4^{256}}\mbox{ copies of }4
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{4}.}.}.}4}4}\\
   \underbrace{^{^{^{^{^{4}.}.}.}4}4}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}}\\
   4^{4^{256}}\mbox{ copies of }4
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{4}.}.}.}4}4}\\
   \underbrace{^{^{^{^{^{4}.}.}.}4}4}\\
   \underbrace{^{^{^{^{^{4}.}.}.}4}4}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}}\\
   \underbrace{4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}}\\
   4^{4^{256}}\mbox{ copies of }4
  \end{matrix}</math> 
| <math>4\uparrow\uparrow\uparrow\uparrow b</math>
|}

===Computing 10↑<sup>''n''</sup>&nbsp;''b''===

We place the numbers <math>10^b</math> in the top row, and fill the left column with values 10. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

{| class="wikitable"
|+ Values of <math>10\uparrow^n b</math> = [[Hyperoperation#Notations|<math>H_{n+2}(10,b)</math>]] = [[Hyperoperation#Notations|<math>10[n+2]b</math>]] = [[Conway chained arrow notation|10 → b → n]]
|-
! {{diagonal split header|''ⁿ''|''b''}}
! 1
! 2
! 3
! 4
! 5
! formula
|-
! 1
| 10 || 100 || 1,000 || 10,000 || 100,000 || <math>10^b</math>
|-
! 2
| 10 || 10,000,000,000 || <math>10^{10,000,000,000}</math>  || <math>10^{10^{10,000,000,000}}</math>  || <math>10^{10^{10^{10,000,000,000}}}</math> || <math>10\uparrow\uparrow b</math>
|-
! 3
| 10 || <math>
  \begin{matrix}
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   10\mbox{ copies of }10
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   10\mbox{ copies of }10
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   10\mbox{ copies of }10
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   10\mbox{ copies of }10
  \end{matrix}</math> || <math>10\uparrow\uparrow\uparrow b</math>
|-
! 4
| 10 || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   10\mbox{ copies of }10
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   10\mbox{ copies of }10
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   10\mbox{ copies of }10
  \end{matrix}</math> || <math>
  \begin{matrix}
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   10\mbox{ copies of }10
  \end{matrix}</math> 
| <math>10\uparrow\uparrow\uparrow\uparrow b</math>
|}

For 2 ≤ ''b'' ≤ 9 the numerical order of the numbers <math>10\uparrow^n b</math> is the [[lexicographical order]] with ''n'' as the most significant number, so for the numbers of these 8 columns the numerical order is simply line-by-line. The same applies for the numbers in the 97 columns with 3 ≤ ''b'' ≤ 99, and if we start from ''n'' = 1 even for 3 ≤ ''b'' ≤ 9,999,999,999.

==See also==
*[[Primitive recursion]]
*[[Hyperoperation]]
*[[Busy beaver]]
*[[Cutler's bar notation]]
*[[Tetration]]
*[[Pentation]]
*[[Ackermann function]]
*[[Graham's number]]
*[[Steinhaus–Moser notation]]

== Notes ==
<references group="nb" />

== References ==
{{Reflist}}

==External links==
* {{mathworld|urlname=KnuthUp-ArrowNotation|title=Knuth Up-Arrow Notation}}
* Robert Munafo, ''[http://www.mrob.com/pub/math/largenum-3.html#hyper5 Large Numbers: Higher hyper operators]''

{{Hyperoperations}}
{{Large numbers}}
{{Donald E. Knuth}}
[[Category:Mathematical notation]]
[[Category:Large numbers]]
[[Category:Donald Knuth]]
[[Category:1976 introductions]]