Arrow spelling

In mathematics , the arrow notation is a method that Donald Ervin Knuth developed in 1976 to write very large numbers. It is closely related to the Ackermann function . The idea is based on repeated exponentiation, just as exponentiation is repeated multiplication and multiplication is repeated addition.

introduction

The multiplication of a natural number can be defined as repeated addition :

${\displaystyle {\begin{matrix}a\cdot b&=&\underbrace {b+b+\dots +b} \\&&a{\mbox{ Kopien von }}b\end{matrix}}}$

For example:

${\displaystyle {\begin{matrix}3\cdot 2&=&\underbrace {2+2+2} &=&6\\&&3{\mbox{ Kopien von }}2\end{matrix}}}$

A natural number as an exponent can be defined as repeated multiplication: ${\displaystyle b}$

${\displaystyle {\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\cdot a\cdot \dots \cdot a} \\&b{\mbox{ Kopien von }}a\end{matrix}}}$

For example:

${\displaystyle {\begin{matrix}3\uparrow 2=3^{2}=&\underbrace {3\cdot 3} &=&9\\&2{\mbox{ Kopien von }}3\end{matrix}}}$

This inspired Knuth to define a "double arrow" operator for repeated exponents:

${\displaystyle {\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow a\uparrow \dots \uparrow a} \\&&b{\mbox{ Kopien von }}a&&b{\mbox{ Kopien von }}a\end{matrix}}}$

For example:

${\displaystyle {\begin{matrix}3\uparrow \uparrow 2&={\ ^{2}3}=&\underbrace {3^{3}} &=&\underbrace {3\uparrow 3} &=&27\\&&2{\mbox{ Kopien von }}3&&2{\mbox{ Kopien von }}3\end{matrix}}}$

This operator is right-associative , which means it is evaluated from right to left.

According to this definition is

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

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

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}}$(Writing out this number in full would take up about 1.37 terabytes of storage space, namely bits) ${\displaystyle 7\,625\,597\,484\,987\cdot {\tfrac {\log 3}{\log 2}}}$

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

etc.

This already leads to some very large numbers, but Knuth expanded his notation even further. He introduced a "triple arrow operator" to represent repeated use of the "double arrow":

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow a\uparrow \uparrow \dots \uparrow \uparrow a} \\&b{\mbox{ Kopien von }}a\end{matrix}}}$

followed by a "quadruple arrow operator":

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a} \\&b{\mbox{ Kopien von }}a\end{matrix}}}$

and so on. The general rule is that a -fold arrow operator becomes a -fold repetition of a -fold arrow operator: ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle (n-1)}$

${\displaystyle {\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{ Kopien von }}a\end{matrix}}}$

Examples:

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

${\displaystyle {\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{ Kopien von }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&7\,625\,597\,484\,987{\mbox{ Kopien von }}3\end{matrix}}}$

notation

In expressions such as , the exponent is usually written superscript in relation to the base . However, many environments - for example programming languages ​​and plain text such as e-mail - do not allow such two-dimensional layouts. The notation was used here . The arrow should be read as 'increasing the exponent'. If the environment does not allow an arrow, the circumflex ^ is used instead . ${\displaystyle a^{b}}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle a\uparrow b}$

The superscript spelling does not lend itself to a generalization. That is why Knuth chose the arrow notation, which can be written in one line instead. ${\displaystyle a^{b}}$

In some programming languages ​​the ^ character is used for another operator, for example in Python for XOR . Here ** is sometimes used as an alternative to , as is also the case in the Very High Speed ​​Integrated Circuit Hardware Description Language (VHDL) and Fortran . The repeated spelling is also used here, which is intended to mean repeated use of the individual operator. So it would be possible to use *** as an equivalent to the double arrow , but this is not common. ${\displaystyle \uparrow }$ ${\displaystyle \uparrow \uparrow }$

definition

The arrow notation is formally defined by

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

for all natural numbers for which applies . ${\displaystyle a,b,n}$ ${\displaystyle b\geq 1,n\geq 1}$

${\displaystyle \uparrow ^{n}}$means here adjacent arrows (e.g. ). ${\displaystyle n}$ ${\displaystyle a\uparrow ^{3}b=a\uparrow \uparrow \uparrow b}$

All arrow operators (normal exponent notation is considered here ) are right-associative operators , i.e. if there are several operators, the expression is evaluated from right to left. For example, in general:, not ; for example is not ${\displaystyle a\uparrow b}$ ${\displaystyle a\uparrow b\uparrow c=a\uparrow (b\uparrow c)}$ ${\displaystyle (a\uparrow b)\uparrow c}$
${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}}$ ${\displaystyle 3^{(3^{3})}=3^{27}=7\,625\,597\,484\,987}$ ${\displaystyle \left(3^{3}\right)^{3}=27^{3}=19\,683.}$

There is a good reason for this legal associativity. Evaluating from left to right would do the same as , so that would not result in a new operator. See also potency tower . ${\displaystyle a\uparrow \uparrow b}$ ${\displaystyle a\uparrow (a\uparrow (b-1))}$ ${\displaystyle \uparrow \uparrow }$

The definition can be extended to a few whole numbers . So you can, for example , and set. However, caution is required when choosing the initial condition for , because then (unlike for larger ones ): and . ${\displaystyle n<1}$ ${\displaystyle a\uparrow ^{0}b=a\cdot b}$ ${\displaystyle a\uparrow ^{-1}b=a+b}$ ${\displaystyle a\uparrow ^{-2}b=b+1}$ ${\displaystyle b=1}$ ${\displaystyle n}$ ${\displaystyle a\uparrow ^{-1}1=a+1}$ ${\displaystyle a\uparrow ^{-2}1=2}$

See also

• Steinhaus-Moser notation
• Hyperoperator
• Chained arrow notation
• Graham's number

literature

• Donald E. Knuth: Coping With Finiteness . In: Science . tape 194 , no. 4271 , December 1976, p. 1235-1236 .

• Guido Walz (Red.): Arrow notation . In: Lexicon of Mathematics . 4. Moo to Sch. Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-0436-3 .