Knuth's up-arrow notation

From Wikipedia, the free encyclopedia

In mathematics, Knuth's up-arrow notation is a method of notation of very large integers introduced by Donald Knuth in 1976. It is closely related to the Ackermann function. The idea is based on iterated exponentiation in much the same way that exponentiation can be similar to iterated multiplication, and multiplication can be similar to iterated addition.

[edit] Introduction

Multiplication by a natural number can be defined as iterated addition:

$\begin{matrix} a\times b & = & \underbrace{a+a+\dots+a} \\ & & b\mbox{ copies of }a \end{matrix} .$

For example,

$\begin{matrix} 3\times 2 & = & \underbrace{3+3} & = & 6\\ & & 2\mbox{ copies of }3 \end{matrix} .$

Exponentiation for a natural power $b$ can be defined as iterated multiplication:

$\begin{matrix} a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\ & b\mbox{ copies of }a \end{matrix} .$

For example,

$\begin{matrix} 3\uparrow 2= 3^2 = & \underbrace{3\times 3} & = & 9\\ & 2\mbox{ copies of }3 \end{matrix} .$

This inspired Knuth to define a “double arrow” operator for iterated exponentiation or tetration:

$\begin{matrix} a\uparrow\uparrow b & = {\ ^{b}a} = & \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} 3\uparrow\uparrow 2 & = {\ ^{2}3} = & \underbrace{3^3} & = & \underbrace{3\uparrow 3} & = & 27 \\ & & 2\mbox{ copies of }3 & & 2\mbox{ copies of }3 \end{matrix} .$

Here and below evaluation is to take place from right to left (as such the operation is right-associative):

According to this definition,

$3\uparrow\uparrow2=3^3=27$

$3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987$

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}$ (just writing out this number in expanded form would require about 1.37 terabytes of storage space, i. e. $7,625,597,484,987 \times \frac{\log 3}{\log 2}$ bits)

$3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7625597484987}}$

etc.

This already leads to some fairly large numbers, but Knuth extended the notation. He went on to define a “triple arrow” operator for iterated application of the “double arrow” operator (also known as pentation):

$\begin{matrix} a\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow a\uparrow\uparrow\dots\uparrow\uparrow a}\\ & b\mbox{ copies of }a \end{matrix}$

followed by a 'quad arrow' operator:

$\begin{matrix} a\uparrow\uparrow\uparrow\uparrow 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 series of ( $n - 1$ )-arrow operators. Symbolically,

$\begin{matrix} a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}\ b= a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow} \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow} \ a\ \dots \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow} \ a \\ \quad\ \ \,n\qquad\ \ \ \underbrace{\quad n_{}\!-\!\!1\quad\ \,n\!-\!\!1\qquad\quad\ \ \ \,n\!-\!\!1\ \ \ } \\ \qquad\qquad\quad\ \ b\mbox{ copies of }a \end{matrix}$

Examples:

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

$\begin{matrix} 3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\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}$

[edit] 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 such two-dimensional layout. 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 doesn't 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.

In the context of the C programming language, the ^ character is the XOR operator. ** is a common alternative to $\uparrow$ for discussion in this context, using the same principle of two symbols meaning repetition of that operator. It is possible that *** could be equivalent to $\uparrow\uparrow$ , but this usage is uncommon.

[edit] 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. With b too large to write b numbers a, this requires using dots and a brace with the number b next to it, indicating the height of the power tower. $a \uparrow \uparrow \uparrow b$ requires a row of such power towers, separated by braces: there are b power towers, including the last with height 1, hence simply the number a. If b is too large to write all these power towers, we use dots to indicate a row of them, and for the number of power towers a "cross-brace" (the number of braces is one less). $a \uparrow \uparrow \uparrow \uparrow b$ requires a row of such rows of power towers; there are b rows of power towers, including the last, which consists of only one "power tower" of height 1, so is simply the number a. If b is too large to write all these rows, we use a "cross-cross-brace" with this number b next to it (the number of cross-braces is one less). And so on.

Since the power notation is in direction "/", the braces are too. A row of them could be written in perpendicular direction "\", and the cross-brace too. A row of cross-braces could then extend in the direction "/", with a cross-cross-brace too, etc.

Example:

For 4 $\uparrow\uparrow\uparrow$ 6 there are six power towers, including the last with height 1, hence simply the number 4; writing out the fifth power tower we have only five:

$\begin{matrix} \underbrace{\begin{matrix} \underbrace{4^{4^{4^{.^{.^{.{4}}}}}}} \\ \underbrace{4^{4^{4^{.^{.^{.{4}}}}}}} \\ \underbrace{4^{4^{4^{.^{.^{.{4}}}}}}} \\ {4^{4^{4^{.^{.^{.{4}}}}}}} \end{matrix}} \\ {4^{4^{4^{4}}}} \end{matrix}$

Using the left-superscript notation for tetration we have one "level of braces" less: $a \uparrow \uparrow \uparrow b$ requires a "tetration tower" in the direction "\", and a brace with the number b next to it, indicating the height of the tetration tower. $a \uparrow \uparrow \uparrow \uparrow b$ requires a row of such tetration towers, separated by braces: there are b tetration towers, including the last with height 1, hence simply the number a. If b is too large to write all these tetration towers, we use a "cross-brace" with this number b next to it. And so on.

Examples:

The previous example becomes

$^{^{^{^{^{4}4}4}4}4}4$

For the fourth Ackermann number $4 \uparrow \uparrow \uparrow \uparrow 4$ there are four tetration towers, including the last with height 1, hence simply the number 4; writing out the third tetration tower we have only three:

$\begin{matrix} \underbrace{\begin{matrix} \underbrace{^{^{^{^{^{^{^{4}.}.}.}4}4}4}4} \\ ^{^{^{^{^{^{^{4}.}.}.}4}4}4}4 \end{matrix}} \\ ^{^{^{^4}4}4}4 \end{matrix}$

[edit] 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. Graham's number is an example. 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 & = & \mbox{hyper}(a,n+2,b) & = & a\to b\to n \\ \mbox{(Knuth)} & & & & \mbox{(Conway)} \end{matrix}$

It is generally suggested that Knuth's arrow should be used for relatively smaller magnitude numbers, and the chained arrow or hyper operators for larger ones.

[edit] Definition

The up-arrow notation is formally defined by

$a\uparrow^n b= \left\{ \begin{matrix} a^b, & \mbox{if }n=1; \\ 1, & \mbox{if }b=0; \\ a\uparrow^{n-1}(a\uparrow^n(b-1)), & \mbox{otherwise} \end{matrix} \right.$

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

All up-arrow operators (including normal exponentiation, $a \uparrow b$ ) are right associative, i.e. evaluation is to take place from right to left in an expression that contains two or more such operators. For example, $a \uparrow b \uparrow c = a \uparrow (b \uparrow c)$ , not $(a \uparrow b) \uparrow c$ ; for example
$3\uparrow\uparrow 3=3^{3^3}$ is $3^{(3^3)}=3^{27}=7625597484987$ not $\left(3^3\right)^3=27^3=19683.$

There is good reason for the choice of this right-to-left order of evaluation. If we used left-to-right evaluation, then $a \uparrow\uparrow b$ would equal $a \uparrow (a \uparrow (b - 1))$ , so that $\uparrow\uparrow$ would not be an essentially new operation. Right associativity is also natural because we can rewrite the iterated arrow expression $a\uparrow^n\cdots\uparrow^na$ that appears in the expansion of $a \uparrow^{n + 1}b$ as $a\uparrow^n\cdots\uparrow^na\uparrow^n1$ , so that all the $a$ s appear as left operands of arrow operators. This is significant since the arrow operators are not commutative.

Writing $(a\uparrow ^m)^b$ for the bth functional power of the function $f(n)=a\uparrow ^m n$ we have $a\uparrow ^n b = (a\uparrow ^{n-1})^b 1$ .

The definition could be extrapolated one step, starting with $a\uparrow^n b= ab$ if n = 0, because exponentiation is repeated multiplication starting with 1. Extrapolating one step more, writing multiplication as repeated addition, is not as straightforward because multiplication is repeated addition starting with 0 instead of 1. "Extrapolating" again one step more, writing addition of n as repeated addition of 1, requires starting with the number a. Compare the definition of the hyper operator, where the starting values for addition and multiplication are also separately specified.

[edit] Tables of values

Computing $2\uparrow^m n$ can be restated in terms of an infinite table. We place the numbers 2 $n$ 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^m n$ = hyper(2, m + 2, n) = 2 → n → m
m\n	1	2	3	4	5	6	7	formula
0	2	4	6	8	10	12	14	$2 n$
1	2	4	8	16	32	64	128	$2 n$
2	2	4	16	65536	$2^{65536}\approx 2.0 \times 10^{19,729}$	$2^{2^{65536}}\approx 10^{6.0 \times 10^{19,728}}$	$2^{2^{2^{65536}}}\approx 10^{10^{6.0 \times 10^{19,728}}}$	$2\uparrow\uparrow n$
3	2	4	65536	$\begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}} \\ 65536\mbox{ copies of }2 \end{matrix}\approx (10\uparrow)^{65531}(6.0 \times 10^{19,728})$				$2\uparrow\uparrow\uparrow n$
4	2	4	$\begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}}\\ 65536\mbox{ copies of }2 \end{matrix}$					$2\uparrow\uparrow\uparrow\uparrow n$

Note: $(10\uparrow)^k$ denotes a functional power of the function $f (n) = 10 n$ (the function also expressed by the suffix -plex as in googolplex).

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

Computing $3\uparrow^m n$

We place the numbers 3 $n$ 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^m n$ = hyper(3, m + 2, n) = 3 → n → m
m\n	1	2	3	4	5	formula
0	3	6	9	12	15	$3 n$
1	3	9	27	81	243	$3 n$
2	3	27	7,625,597,484,987	$3 7,625,597,484,987$		$3\uparrow\uparrow n$
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 n$
4	3	$\begin{matrix} \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\ 7,625,597,484,987\mbox{ copies of }3 \end{matrix}$				$3\uparrow\uparrow\uparrow\uparrow n$

Computing $10\uparrow^m n$

We place the numbers 10 $n$ 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^m n$ = hyper(10, m + 2, n) = 10 → n → m
m\n	1	2	3	4	5	formula
0	10	20	30	40	50	$10 n$
1	10	100	1,000	10,000	100,000	$10 n$
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 n$
3	10	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10\mbox{ copies of }10 \end{matrix}$	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10^{10}\mbox{ copies of }10 \end{matrix}$	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10^{10^{10}}\mbox{ copies of }10 \end{matrix}$		$10\uparrow\uparrow\uparrow n$
4	10	$\begin{matrix} \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\ 10\mbox{ copies of }10 \end{matrix}$	$\begin{matrix} \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\ 10^{10}\mbox{ copies of }10 \end{matrix}$			$10\uparrow\uparrow\uparrow\uparrow n$

Note that for 2 ≤ n ≤ 9 the numerical order of the numbers $10\uparrow^m n$ is the lexicographical order with m 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 ≤ n ≤ 99, and if we start from m = 1 even for 3 ≤ n ≤ 9,999,999,999.

[edit] See also

[edit] References

Knuth, Donald E., "Coping With Finiteness", Science vol. 194 n. 4271 (Dec 1976), pp. 1235-1242.
Eric W. Weisstein, Arrow Notation at MathWorld.
Robert Munafo, Large Numbers

Knuth's up-arrow notation

From Wikipedia, the free encyclopedia

Contents

[edit] Introduction

[edit] Notation

[edit] Writing out up-arrow notation in terms of powers

[edit] Generalizations

[edit] Definition

[edit] Tables of values

[edit] See also

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages