Knuthova notacija

V matematiki je Knuthova gornjepuščična notacija metoda zapisovanja zelo velikih celih števil. Izumil jo je Donald Knuth leta 1976.

Stopnjevanje

Množenje lahko na naslednji način zapišemo v obliki seštevanja:

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

Za primer:

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

Tudi potenciranje se da zapisati v obliki množenja:

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

Za primer:

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

Enako se zgodi tudi z tetracijo:

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

Za primer:

${\begin{matrix}3\uparrow \uparrow 2&={\ ^{2}3}=&\underbrace {3^{3}} &=&\underbrace {3\uparrow 3} &=&27\\&&2{\mbox{ kopiji }}3&&2{\mbox{ kopiji }}3\end{matrix}}.$

Primeri tetracije zapisane v Knuthovi gornjepuščični notaciji:

$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^{7625597484987}$ (samo zapis tega števila bi zavzel približno 1,37 terabajta prostora)

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

itn.

V Knuthovi gornjepuščični notaciji pa se da zapisati tudi pentacijo:

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

Heksacija:

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

In tako naprej.

Pravilo pa je:

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

Primeri:

$3\uparrow \uparrow 2=3\uparrow 3=27$

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