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 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), pentation (n = 5), etc.

Various notations have been used to represent hyperoperations. One such notation is $H_{n}(a,b)$. Another notation is $a[n]b$, an infix notation which is convenient for ASCII. The notation $a[n]b$ is known as 'square bracket notation'.

Knuth's up-arrow notation $\uparrow$ is an alternative notation. It is obtained by replacing $[n]$ in the square bracket notation by $n-2$ arrows.

For example:

• the single arrow $\uparrow$ represents exponentiation (iterated multiplication)

$2\uparrow 4=H_{3}(2,4)=2[3]4=2\times (2\times (2\times 2))=2^{4}=16$

• the double arrow $\uparrow \uparrow$ represents tetration (iterated exponentiation)

$2\uparrow \uparrow 4=H_{4}(2,4)=2[4]4=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^{2}}}=2^{16}=65536$

• the triple arrow $\uparrow \uparrow \uparrow$ represents pentation (iterated tetration)

${\begin{aligned}2\uparrow \uparrow \uparrow 4=H_{5}(2,4)=2[5]4={2^{65536}}&=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 ))} \\&2\uparrow \uparrow 4{\mbox{ copies of }}2\\\end{aligned}}$

The general definition of the up-arrow notation is as follows (for $a\geq 0,n\geq 1,b\geq 0$):

$a\uparrow ^{n}b=H_{n+2}(a,b)=a[n+2]b$

Here, $\uparrow ^{n}$ stands for n arrows, so for example

$2\uparrow \uparrow \uparrow \uparrow 3=2\uparrow ^{4}3$.

Introduction

The hyperoperations naturally extend the arithmetical operations of addition and multiplication as follows.

Addition by a natural number is defined as iterated incrementation:

${\begin{matrix}H_{1}(a,b)=a[1]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:

${\begin{matrix}H_{2}(a,b)=a[2]b=a\times b=&\underbrace {a+a+\dots +a} \\&b{\mbox{ copies of }}a\end{matrix}}$

For example,

${\begin{matrix}3\times 4&=&\underbrace {3+3+3+3} &=&12\\&&4{\mbox{ copies of }}3\end{matrix}}$

Exponentiation for a natural power $b$ is defined as iterated multiplication, which Knuth denoted by a single up-arrow:

${\begin{matrix}a\uparrow b=H_{3}(a,b)=a[3]b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ copies of }}a\end{matrix}}$

For example,

${\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”:

${\begin{matrix}a\uparrow \uparrow b=H_{4}(a,b)=a[4]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}}$

For example,

${\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}}$

Expressions are evaluated from right to left, as the operators are defined to be right-associative.

According to this definition,

$3\uparrow \uparrow 2=3^{3}=27$

$3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987$

$3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}$

$3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}\approx 3^{1.2580143\times 10^{3638334640024}}$

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”:

${\begin{matrix}a\uparrow \uparrow \uparrow b=H_{5}(a,b)=a[5]b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}$

Hexation, defined as iterated pentation, is represented by the “quadruple arrow”:

${\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=H_{6}(a,b)=a[6]b=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}$

and so on. The general rule is that an $n$-arrow operator expands into a right-associative series of ($n-1$)-arrow operators. Symbolically,

${\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}}$

Examples:

$3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987$

${\begin{matrix}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3{\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}}$

Notation

In expressions such as $a^{b}$, the notation for exponentiation is usually to write the exponent $b$ as a superscript to the base number $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\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}$ doesn't lend itself well to generalization, which explains why Knuth chose to work from the inline notation $a\uparrow b$ instead.

$a\uparrow ^{n}b$ is a shorter alternative notation for n uparrows. Thus $a\uparrow ^{4}b=a\uparrow \uparrow \uparrow \uparrow b$.

Knuth's arrows have become quite popular, maybe because $\uparrow ^{n}$ is a stronger logo than for instance $[n]$.

Writing out up-arrow notation in terms of powers

Attempting to write $a\uparrow \uparrow b$ using the familiar superscript notation gives a power tower.

For example: $a\uparrow \uparrow 4=a\uparrow (a\uparrow (a\uparrow a))=a^{a^{a^{a}}}$

If 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\uparrow \uparrow b=\underbrace {a^{a^{.^{.^{.{a}}}}}} _{b}$

Continuing with this notation, $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\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}}}$

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

$a\uparrow \uparrow \uparrow b=\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}b$

Furthermore, $a\uparrow \uparrow \uparrow \uparrow b$ 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:

$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$

And more generally:

$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}$

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

Using tetration

The tetration notation $^{b}a$ allows us to make these diagrams slightly simpler while still employing a geometric representation (we could call these tetration towers).

$a\uparrow \uparrow b={}^{b}a$

$a\uparrow \uparrow \uparrow b=\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{b}$

$a\uparrow \uparrow \uparrow \uparrow b=\left.\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{\underbrace {\vdots } _{a}}}\right\}b$

Finally, as an example, the fourth Ackermann number $4\uparrow ^{4}4$ could be represented as:

$\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}}$

Generalizations

Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an n-arrow operator $\uparrow ^{n}$ is useful (and also for descriptions with a variable number of arrows), or equivalently, hyper operators.

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.

${\begin{matrix}a\uparrow ^{n}b&=&a[n+2]b&=&a\to b\to n\\{\mbox{(Knuth)}}&&{\mbox{(hyperoperation)}}&&{\mbox{(Conway)}}\end{matrix}}$

Definition

Without reference to Hyperoperation the up-arrow operators can be formally defined by

$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}}$

for all integers $a,b,n$ with $a\geq 0,n\geq 1,b\geq 0$.

This definition uses exponentiation $(a\uparrow ^{1}b=a\uparrow b=a^{b})$ as the base case, and tetration $(a\uparrow ^{2}b=a\uparrow \uparrow b)$ as repeated exponentiation. This is equivalent to the hyperoperation sequence except it omits the three more basic operations of succession, addition and multiplication.

One can alternatively choose multiplication $(a\uparrow ^{0}b=a\times b)$ as the base case and iterate from there. Then exponentiation becomes repeated multiplication. The formal definition would be

$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}}$

for all integers $a,b,n$ with $a\geq 0,n\geq 0,b\geq 0$.

Remark however that Knuth did not define the "nil-arrow" ($\uparrow ^{0}$). 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:

$H_{n}(a,b)=a[n]b=a\uparrow ^{n-2}b{\text{ for }}n\geq 0.$

The up-arrow operation is a right-associative operation, that is, $a\uparrow b\uparrow c$ is understood to be $a\uparrow (b\uparrow c)$, instead of $(a\uparrow b)\uparrow c$. If ambiguity is not an issue parentheses are sometimes dropped.

Tables of values

Computing 0↑ⁿ b

Computing $0\uparrow ^{n}b=H_{n+2}(0,b)=0[n+2]b$ results in

0, when n = 0 

1, when n = 1 and b = 0  

0, when n = 1 and b > 0  

1, when n > 1 and b is even (including 0)

0, when n > 1 and b is odd

Computing 2↑ⁿ b

Computing $2\uparrow ^{n}b$ can be restated in terms of an infinite table. We place the numbers $2^{b}$ 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.

Values of $2\uparrow ^{n}b$ = $H_{n+2}(2,b)$ = $2[n+2]b$ = 2 → b → n

b ⁿ	1	2	3	4	5	6	formula
1	2	4	8	16	32	64	$2^{b}$
2	2	4	16	65536	$2^{65\,536}\approx 2.0\times 10^{19\,728}$	$2^{2^{65\,536}}\approx 10^{6.0\times 10^{19\,727}}$	$2\uparrow \uparrow b$
3	2	4	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ copies of }}2\end{matrix}}$	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ copies of }}2\end{matrix}}$	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ copies of }}2\end{matrix}}$	$2\uparrow \uparrow \uparrow b$
4	2	4	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ copies of }}2\end{matrix}}$				$2\uparrow \uparrow \uparrow \uparrow b$

The table is the same as that of the Ackermann function, except for a shift in $n$ and $b$, and an addition of 3 to all values.

Computing 3↑ⁿ b

We place the numbers $3^{b}$ 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.

Values of $3\uparrow ^{n}b$ = $H_{n+2}(3,b)$ = $3[n+2]b$ = 3 → b → n

b ⁿ	1	2	3	4	5	formula
1	3	9	27	81	243	$3^{b}$
2	3	27	7,625,597,484,987	$3^{7{,}625{,}597{,}484{,}987}$	$3^{3^{7{,}625{,}597{,}484{,}987}}$	$3\uparrow \uparrow b$
3	3	7,625,597,484,987	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7{,}625{,}597{,}484{,}987{\mbox{ copies of }}3\end{matrix}}$			$3\uparrow \uparrow \uparrow b$
4	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7{,}625{,}597{,}484{,}987{\mbox{ copies of }}3\end{matrix}}$				$3\uparrow \uparrow \uparrow \uparrow b$

Computing 4↑ⁿ b

We place the numbers $4^{b}$ 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.

Values of $4\uparrow ^{n}b$ = $H_{n+2}(4,b)$ = $4[n+2]b$ = 4 → b → n

b ⁿ	1	2	3	4	5	formula
1	4	16	64	256	1024	$4^{b}$
2	4	256	$1.3407807930\times 10^{154}$	$4^{1.3407807930\times 10^{154}}$	$4^{4^{1.3407807930\times 10^{154}}}$	$4\uparrow \uparrow b$
3	4	$4^{1.3407807930\times 10^{154}}$	${\begin{matrix}\underbrace {4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}} \\4^{1.3407807930\times 10^{154}}{\mbox{ copies of }}4\end{matrix}}$			$4\uparrow \uparrow \uparrow b$
4	4	${\begin{matrix}\underbrace {4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}} \\\underbrace {4_{}^{4^{{}^{.\,^{.\,^{.\,^{4}}}}}}} \\4^{1.3407807930\times 10^{154}}{\mbox{ copies of }}4\end{matrix}}$				$4\uparrow \uparrow \uparrow \uparrow b$

Computing 10↑ⁿ b

We place the numbers $10^{b}$ 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.

Values of $10\uparrow ^{n}b$ = $H_{n+2}(10,b)$ = $10[n+2]b$ = 10 → b → n

b ⁿ	1	2	3	4	5	formula
1	10	100	1,000	10,000	100,000	$10^{b}$
2	10	10,000,000,000	$10^{10,000,000,000}$	$10^{10^{10,000,000,000}}$	$10^{10^{10^{10,000,000,000}}}$	$10\uparrow \uparrow b$
3	10	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10{\mbox{ copies of }}10\end{matrix}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10{\mbox{ copies of }}10\end{matrix}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10{\mbox{ copies of }}10\end{matrix}}$		$10\uparrow \uparrow \uparrow b$
4	10	${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10{\mbox{ copies of }}10\end{matrix}}$	${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10{\mbox{ copies of }}10\end{matrix}}$			$10\uparrow \uparrow \uparrow \uparrow b$

For 2 ≤ b ≤ 9 the numerical order of the numbers $10\uparrow ^{n}b$ 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

External links

• Weisstein, Eric W. "Knuth Up-Arrow Notation". MathWorld.
• Robert Munafo, Large Numbers: Higher hyper operators