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 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 operations of addition (n = 1), multiplication (n = 2), exponentiation (n = 3), tetration (n = 4), etc. Various notations have been used to represent hyperoperations. One such notation is H n ( a , b ) {\displaystyle H_{n}(a,b)} . Knuth's up-arrow notation ↑ {\displaystyle \uparrow } is another. For example:
the single arrow ↑ {\displaystyle \uparrow } represents exponentiation (iterated multiplication) 2 ↑ 4 = H 3 ( 2 , 4 ) = 2 × ( 2 × ( 2 × 2 ) ) = 2 4 = 16 {\displaystyle 2\uparrow 4=H_{3}(2,4)=2\times (2\times (2\times 2))=2^{4}=16}
the double arrow ↑↑ {\displaystyle \uparrow \uparrow } represents tetration (iterated exponentiation) 2 ↑↑ 4 = H 4 ( 2 , 4 ) = 2 ↑ ( 2 ↑ ( 2 ↑ 2 ) ) = 2 2 2 2 = 2 16 = 65 , 536 {\displaystyle 2\uparrow \uparrow 4=H_{4}(2,4)=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^{2}}}=2^{16}=65,536}
the triple arrow ↑↑↑ {\displaystyle \uparrow \uparrow \uparrow } represents pentation (iterated tetration) 2 ↑↑↑ 4 = H 5 ( 2 , 4 ) = 2 ↑↑ ( 2 ↑↑ ( 2 ↑↑ 2 ) ) = 2 ↑↑ ( 2 ↑↑ ( 2 ↑ 2 ) ) = 2 ↑↑ ( 2 ↑↑ 4 ) = 2 ↑ ( 2 ↑ ( 2 ↑ ⋯ ) ) ⏟ = 2 2 ⋯ 2 ⏟ 2 ↑↑ 4 copies of 2 65,536 2's {\displaystyle {\begin{aligned}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 \cdots ))} \;=\;\underbrace {\;2^{2^{\cdots ^{2}}}} \\&\;\;\;\;\;2\uparrow \uparrow 4{\text{ copies of }}2\;\;\;\;\;{\text{65,536 2's}}\\\end{aligned}}}
The general definition of the up-arrow notation is as follows (for a ≥ 0 , n ≥ 1 , b ≥ 0 {\displaystyle a\geq 0,n\geq 1,b\geq 0} ):
a ↑ n b = H n + 2 ( a , b ) = a [ n + 2 ] b . {\displaystyle a\uparrow ^{n}b=H_{n+2}(a,b)=a[n+2]b.}
Here, ↑ n {\displaystyle \uparrow ^{n}} stands for n arrows, so for example
2 ↑↑↑↑ 3 = 2 ↑ 4 3 , {\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3=2\uparrow ^{4}3,}
and the square brackets used in the far right hand side expression is 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:
H 1 ( a , b ) = a + b = a + 1 + 1 + ⋯ + 1 ⏟ b copies of 1 {\displaystyle {\begin{matrix}H_{1}(a,b)=a+b=&a+\underbrace {1+1+\dots +1} \\&b{\mbox{ copies of }}1\end{matrix}}}
Multiplication by a natural number is defined as iterated addition:
H 2 ( a , b ) = a × b = a + a + ⋯ + a ⏟ b copies of a {\displaystyle {\begin{matrix}H_{2}(a,b)=a\times b=&\underbrace {a+a+\dots +a} \\&b{\mbox{ copies of }}a\end{matrix}}}
For example,
4 × 3 = 4 + 4 + 4 ⏟ = 12 3 copies of 4 {\displaystyle {\begin{matrix}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3{\mbox{ copies of }}4\end{matrix}}}
Exponentiation for a natural power b {\displaystyle b} is defined as iterated multiplication, which Knuth denoted by a single up-arrow:
a ↑ b = H 3 ( a , b ) = a b = a × a × ⋯ × a ⏟ b copies of a {\displaystyle {\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}}}
For example,
4 ↑ 3 = 4 3 = 4 × 4 × 4 ⏟ = 64 3 copies of 4 {\displaystyle {\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3{\mbox{ copies of }}4\end{matrix}}}
Tetration is defined as iterated exponentiation, which Knuth denoted by a "double arrow":
a ↑↑ b = H 4 ( a , b ) = a a
. . . a ⏟ = a ↑ ( a ↑ ( ⋯ ↑ a ) ) ⏟ b copies of a b copies of a {\displaystyle {\begin{matrix}a\uparrow \uparrow b=H_{4}(a,b)=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\cdots \uparrow a))} \\&b{\mbox{ copies of }}a&&b{\mbox{ copies of }}a\end{matrix}}}
For example,
4 ↑↑ 3 = 4 4 4 ⏟ = 4 ↑ ( 4 ↑ 4 ) ⏟ = 4 256 3 copies of 4 3 copies of 4 {\displaystyle {\begin{matrix}4\uparrow \uparrow 3=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}&&\\&3{\mbox{ copies of }}4&&3{\mbox{ copies of }}4\end{matrix}}}
Expressions are evaluated from right to left, as the operators are defined to be right-associative. According to this definition,
3 ↑↑ 2 = 3 3 = 27 {\displaystyle 3\uparrow \uparrow 2=3^{3}=27}
3 ↑↑ 3 = 3 3 3 = 3 27 = 7 , 625 , 597 , 484 , 987 {\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}
3 ↑↑ 4 = 3 3 3 3 = 3 3 27 = 3 7625597484987 {\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}}
3 ↑↑ 5 = 3 3 3 3 3 = 3 3 3 27 = 3 3 7625597484987 {\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}}
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":
a ↑↑↑ b = H 5 ( a , b ) = a
↑↑ ( a ↑↑ ( ⋯ ↑↑ a ) ) ⏟ b copies of a {\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=H_{5}(a,b)=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\cdots \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}
Hexation, defined as iterated pentation, is represented by the "quadruple arrow":
a ↑↑↑↑ b = H 6 ( a , b ) = a
↑↑↑ ( a ↑↑↑ ( ⋯ ↑↑↑ a ) ) ⏟ b copies of a {\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=H_{6}(a,b)=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\cdots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}
and so on. The general rule is that an n {\displaystyle n} -arrow operator expands into a right-associative series of ( n − 1 {\displaystyle n-1} )-arrow operators. Symbolically,
a ↑
↑ ⋯ ↑ ⏟ n b = a ↑ ⋯ ↑ ⏟ n − 1 ( a ↑
⋯ ↑ ⏟ n − 1 ( ⋯ ↑
⋯ ↑ ⏟ n − 1 a ) ) ⏟ b copies of a {\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\cdots \!\!\uparrow } _{n}\ b=\underbrace {a\ \underbrace {\uparrow \!\!\cdots \!\!\uparrow } _{n-1}\ (a\ \underbrace {\uparrow _{}\!\!\cdots \!\!\uparrow } _{n-1}\ (\cdots \ \underbrace {\uparrow _{}\!\!\cdots \!\!\uparrow } _{n-1}\ a))} _{b{\text{ copies of }}a}\end{matrix}}}
Examples:
3 ↑↑↑ 2 = 3 ↑↑ 3 = 3 3 3 = 3 27 = 7 , 625 , 597 , 484 , 987 {\displaystyle 3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}
3 ↑↑↑ 3 = 3 ↑↑ ( 3 ↑↑ 3 ) = 3 ↑↑ ( 3 ↑ 3 ↑ 3 ) = 3 ↑ 3 ↑ ⋯ ↑ 3 ⏟ 3 ↑ 3 ↑ 3 copies of 3 = 3 ↑ 3 ↑ ⋯ ↑ 3 ⏟ 7,625,597,484,987 copies of 3 = 3 3 3 3 ⋅ ⋅ ⋅ ⋅ 3 ⏟ 7,625,597,484,987 copies of 3 {\displaystyle {\begin{aligned}3\uparrow \uparrow \uparrow 3&=3\uparrow \uparrow (3\uparrow \uparrow 3)\\&=3\uparrow \uparrow (3\uparrow 3\uparrow 3)\\&={\begin{matrix}\underbrace {3\uparrow 3\uparrow \cdots \uparrow 3} \\3\uparrow 3\uparrow 3{\mbox{ copies of }}3\end{matrix}}\\&={\begin{matrix}\underbrace {3\uparrow 3\uparrow \cdots \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}}\end{aligned}}}
Notation In expressions such as a b {\displaystyle a^{b}} , the notation for exponentiation is usually to write the exponent b {\displaystyle b} as a superscript to the base number a {\displaystyle a} . But many environments — such as programming languages and plain-text e-mail — do not support superscript typesetting. People have adopted the linear notation a ↑ b {\displaystyle a\uparrow b} 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 a b {\displaystyle a^{b}} doesn't lend itself well to generalization, which explains why Knuth chose to work from the inline notation a ↑ b {\displaystyle a\uparrow b} instead.
a ↑ n b {\displaystyle a\uparrow ^{n}b} is a shorter alternative notation for n up arrows. Thus a ↑ 4 b = a ↑↑↑↑ b {\displaystyle a\uparrow ^{4}b=a\uparrow \uparrow \uparrow \uparrow b} .
Writing out up-arrow notation in terms of powers Attempting to write a ↑↑ b {\displaystyle a\uparrow \uparrow b} using the familiar superscript notation gives a power tower.
For example: a ↑↑ 4 = a ↑ ( a ↑ ( a ↑ a ) ) = a a a a {\displaystyle a\uparrow \uparrow 4=a\uparrow (a\uparrow (a\uparrow a))=a^{a^{a^{a}}}}
If b {\displaystyle b} is a variable (or is too large), the power tower might be written using dots and a note indicating the height of the tower.
a ↑↑ b =
a a . . . a ⏟ b {\displaystyle a\uparrow \uparrow b={}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{b}}
Continuing with this notation, a ↑↑↑ b {\displaystyle a\uparrow \uparrow \uparrow b} could be written with a stack of such power towers, each describing the size of the one above it.
a ↑↑↑ 4 = a ↑↑ ( a ↑↑ ( a ↑↑ a ) ) = a a . . . a ⏟ a a . . . a ⏟ a a . . . a