Knuthova notacija

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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

Stopnjevanje[uredi | uredi kodo]

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\uparrow2=3^3=27
3\uparrow\uparrow3=3^{3^3}=3^{27}=7,625,597,484,987
3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987} (samo pisanje tega števili bi zavzelo približno 1.37 Terabyta prostora)
3\uparrow\uparrow5=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\uparrow2 = 3\uparrow3 = 27

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}