Knuth's Up-arrow Notation Website Links For
Notation 		 

Information About

Knuth's Up-arrow Notation
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




INTRODUCTION


Multiplication by a Natural Number can be defined as iterated Addition :
:
\begin{matrix}
a b & = & \underbrace{a_{}+a+\dots+a} \
& & b\mbox{ copies of }a
\end{matrix}


and Exponentiation for a natural power b can be defined as iterated multiplication:
:
\begin{matrix}
a\uparrow b= a^b = & \underbrace{a_{} imes a imes\dots imes a}\
& b\mbox{ copies of }a
\end{matrix}


which inspired Knuth to define a 'double arrow' Operator for iterated exponentiation or Tetration :
:
\begin{matrix}
a\uparrow\uparrow b & = & \underbrace{a_{}^{a^}}}} &
= & \underbrace{a_{}\uparrow a\uparrow\dots\uparrow a}
\
& & b\mbox{ copies of }a
& & b\mbox{ copies of }a
\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}\,\! (when expanded, this would fill a dozen moderately large hard drives)
: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}



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 Language s and plain-text E-mail — do not support such two-dimensional layout. People have adopted the linear notation ''a''↑''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 for generalization, which explains why Knuth chose to work from the inline notation ''a''↑''b'' instead.

  • --- is a common alternative to ↑ 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 ↑↑, but this usage is uncommon.



GENERALIZATIONS

Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an ''n''-arrow operator ↑''n'' is useful (and also for descriptions with a variable number of arrows), or equivalently, Hyper Operator s.

Some numbers are so large that even that notation is not sufficient. Graham's Number is an example. The Conway Chained Arrow 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 o b o 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.


DEFINITION


The up-arrow notation is formally defined by

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

for all integers ''a'', ''b'' and ''n'' with ''b'' ≥ 0 and ''n'' ≥ 1.

All up-arrow operators (including normal exponentiation, ''a''↑''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''↑''b''↑''c'' = ''a''↑(''b''↑''c''), not (''a''↑''b'')↑''c''; for example

3\uparrow\uparrow 3=3^{3^3} \mbox{ is }3^{(3^3)}=3^{27}=7625597484987 \mbox{ not } \left(3^3 ight)^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''↑↑''b'' would equal
''a''↑(''a''↑(''b''-1)), so that ↑↑ 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''↑''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 .


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.


65536\mbox{ copies of }2 \end{matrix}\approx (10\uparrow)^{65531}(6.0 imes 10^{19,728})


65536\mbox{ copies of }2


  { Border "1" cellpadding="2"


7,625,597,484,987\mbox{ copies of }3


  { Border "1" cellpadding="2"


10\mbox{ copies of }10