Notacja strzałkowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Notacja strzałkowa Knutha – metoda zapisywania bardzo dużych liczb wprowadzona przez amerykańskiego matematyka Donalda Knutha w 1976[1]. Podstawowa idea tej metody jest oparta na iterowanym potęgowaniu, w sposób podobny do tego jak potęgowanie jest iterowanym mnożeniem, mnożenie jest iterowanym dodawaniem, a dodawanie jest iterowaną inkrementacją. Celem tej notacji było zapisanie bardzo dużych liczb, których nawet zapisanie w postaci wykładniczej było trudne lub niemożliwe do wykonania.

Definicja[edytuj | edytuj kod]


a\uparrow^n b=\left\{
\begin{array}{ll}
1 & \mbox{dla }b=0 \\
a^b & \mbox{dla }n=1  \\
a\uparrow^{n-1}(a\uparrow^n(b-1)) & \mbox{dla }n>1 \\
\end{array}
\right.

Dodatkowo w sekcji Inne przykłady wykazano, że:

a\uparrow^n 1 = a

Przykłady[edytuj | edytuj kod]

3\uparrow\uparrow 4 = 3\uparrow 3\uparrow 3\uparrow 3 = 3^{3^{3^3}}= 3^{7625597484987}

3\uparrow\uparrow\uparrow 5 = 3\uparrow\uparrow (3\uparrow\uparrow (3\uparrow\uparrow (3 \uparrow\uparrow 3))) = 3\uparrow\uparrow 3\uparrow\uparrow 3\uparrow\uparrow 3 \uparrow\uparrow 3

3\uparrow^3 3 = 3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow (3\uparrow\uparrow\uparrow 2) = 3\uparrow\uparrow (3\uparrow\uparrow 3) = 3\uparrow\uparrow (3\uparrow 3 \uparrow 3) = 3\uparrow\uparrow (3\uparrow 3^3) = 3\uparrow\uparrow (3^{3^3})

Opis notacji[edytuj | edytuj kod]

Dla skrócenia zapisu dużą ilość strzałek zastępuje się ich liczbą umieszczoną po prawej stronie strzałki w indeksie górnym:

a\uparrow\uparrow\uparrow b = a\uparrow^3 b

a\uparrow\uparrow\uparrow\uparrow b = a\uparrow^4 b

a\uparrow\uparrow...\uparrow\uparrow b = a\uparrow^n b

Konstrukcja[edytuj | edytuj kod]

a\uparrow^1 b = a\times a\times ... \times a

a\uparrow^2 b = a\uparrow a\uparrow ... \uparrow a

a\uparrow^3 b = a\uparrow\uparrow a\uparrow\uparrow ... \uparrow\uparrow a

a\uparrow^4 b = a\uparrow\uparrow\uparrow a\uparrow\uparrow\uparrow ... \uparrow\uparrow\uparrow a

a\uparrow^n b = a \uparrow^{n-1} a \uparrow^{n-1} ... \uparrow^{n-1} a

gdzie a występuje po prawej stronie równań zawsze dokładnie b razy.

Inne przykłady[edytuj | edytuj kod]

  • a\uparrow 1=a^1=a.
a\uparrow\uparrow 1= a\uparrow (a\uparrow\uparrow 0)=a\uparrow 1=a,
a\uparrow^{n+1} 1=a\uparrow^n (a \uparrow^{n+1} 0)= a\uparrow^n 1,
a stąd indukcyjnie uzasadniamy, że  a\uparrow^n 1=a dla wszystkich n\in {\mathbb N}.
  • 2\uparrow 2 = 2^2 = 4,
2\uparrow\uparrow 2 = 2\uparrow (2\uparrow\uparrow 1) = 2\uparrow 2=4,
2\uparrow^{n+1} 2 = 2\uparrow^n (2\uparrow^{n+1} 1) = 2\uparrow^n 2
i stąd indukcyjnie uzasadniamy, że  2\uparrow^n 2=4 dla wszystkich n\in {\mathbb N}.
  • 3\uparrow 3 = 3^3 = 27
3\uparrow^2 3 = 3\uparrow\uparrow 3 = 3 \uparrow (3 \uparrow 3) = 3\uparrow 3^3 = 3\uparrow 27 = 7625597484987
3\uparrow^3 3 = 3\uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow (3 \uparrow\uparrow 3) = 3 \uparrow\uparrow 7625597484987 = 3 \uparrow 3 \uparrow 3 \uparrow \cdots \uparrow 3  ← (7625597484987 trójek)

Liczba Grahama[edytuj | edytuj kod]

 Osobny artykuł: Liczba Grahama.

Oznaczmy G_{1}=3\uparrow^4 3. Wtedy G_{2}=3\uparrow^{G_1} 3, G_{3}=3\uparrow^{G_2} 3, itd. Liczbę G_{64} nazywamy liczbą Grahama.

Przypisy

  1. Knuth Up-Arrow Notation (ang.). mathworld.wolfram.com. [dostęp 2014-04-26].