In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976. It is closely related to the Ackermann function and especially to the hyperoperation sequence. The idea is based on the fact that multiplication can be viewed as iterated addition and exponentiation as iterated multiplication. Continuing in this manner leads to tetration (iterated exponentiation) and to the remainder of the hyperoperation sequence, which is commonly denoted using Knuth arrow notation.
Contents
Introduction
The ordinary arithmetical operations of addition, multiplication, and exponentiation are naturally extended into a sequence of hyperoperations as follows.
Multiplication by a natural number is defined as iterated addition:
For example,
Exponentiation for a natural power
For example,
To extend the sequence of operations beyond exponentiation, Knuth defined a “double arrow” operator to denote iterated exponentiation (tetration):
For example,
Here and below evaluation is to take place from right to left, as Knuth's arrow operators (just like exponentiation) are defined to be right-associative.
According to this definition,
This already leads to some fairly large numbers, but Knuth extended the notation. He went on to define a “triple arrow” operator for iterated tetration (pentation):
followed by a “quadruple arrow“ operator for iterated pentation (hexation):
and so on. The general rule is that an
Examples:
The notation
Notation
In expressions such as
The superscript notation
Writing out up-arrow notation in terms of powers
Attempting to write
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.
Continuing with this notation,
Again, if b is a variable or is too large, the stack might be written using dots and a note indicating its height.
Furthermore,
And more generally:
This might be carried out indefinitely to represent
Using tetration
The tetration notation
Finally, as an example, the fourth Ackermann number
Generalizations
Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an n-arrow operator
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.
It is generally suggested that Knuth's arrow should be used for smaller magnitude numbers, and the chained arrow or hyper operators for larger ones.
Definition
The up-arrow notation is formally defined by
for all integers
This definition takes multiplication as the basic operation
All up-arrow operators (including normal exponentiation,
Note that due to right-associativity we have, for
where each
for all integers
Computing 2↑mn
Computing
The table is the same as that of the Ackermann function, except for a shift in
Computing 3↑mn
We place the numbers
Computing 10↑mn
We place the numbers
Note that for 2 ≤ n ≤ 9 the numerical order of the numbers
Numeration systems based on the hyperoperation sequence
R. L. Goodstein, with a system of notation different from Knuth arrows, used the sequence of hyperoperators here denoted by
The remainder of this section will use the superscripts to denote the hyperoperators.
Unnecessary parentheses can be avoided by giving higher-level operators higher precedence in the order of evaluation; thus,
level-1 representations have the form b [1] X, with X also of this form;
level-2 representations have the form b [2] X [1] Y, with X,Y also of this form;
level-3 representations have the form b [3] X [2] Y [1] Z, with X,Y,Z also of this form;
level-4 representations have the form b [4] X [3] Y [2] Z [1] W, with X,Y,Z,W also of this form;
and so on.
Note that in this type of base-b hereditary representation, the base itself appears in the expressions, as well as "digits" from the set {0, 1, ..., b-1}. This compares to ordinary base-2 representation when the latter is written out in terms of the base b; e.g., in ordinary base-2 notation, 6 = (110)2 = 2 [3] 2 [2] 1[1] 2 [3] 1 [2] 1[1] 2 [3] 0 [2] 0, whereas the level-3 base-2 hereditary representation is 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0). The hereditary representations can be abbreviated by omitting any instances of [1] 0, [2] 1, [3] 1, [4] 1, etc.; for example, the above level-3 base-2 representation of 6 abbreviates to 2 [3] 2 [1] 2.
Examples: The unique base-2 representations of the number 266, at levels 1, 2, 3, 4, and 5 are as follows:
Level 1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (with 133 2s) Level 2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1) Level 3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2 Level 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2 Level 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2