Notacja strzałkowa

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 praktycznie niemożliwe do wykonania. Tempo wzrostu w szybko rosnącej hierarchii wynosi ${\displaystyle f_{\omega }(n).}$

Definicja

Z potęgowaniem jako podstawą:

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

dla wszystkich liczb całkowitych ${\displaystyle a,b,n}$ z ${\displaystyle a\geqslant 0,n\geqslant 1,b\geqslant 0.}$

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

${\displaystyle a\uparrow ^{n}1=a}$

Z mnożeniem jako podstawą^[2]:

${\displaystyle a\uparrow ^{n}b=\left\{{\begin{array}{l}a*b&{\mbox{dla }}n=0\\1&{\mbox{dla }}n\geqslant 1\ {\mbox{i }}\ b=0\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))&{\mbox{inaczej}}\end{array}}\right.}$

dla wszystkich nieujemnych liczb całkowitych ${\displaystyle a,b,n.}$

Dla ${\displaystyle n=1}$ otrzymamy zwykłe potęgowanie ${\displaystyle (3\uparrow 4=3^{4}),}$ dla ${\displaystyle n=2}$ tetrację, dla ${\displaystyle n=3}$ pentację(inne języki) itd. (ang. n-hyperoperation(inne języki))^[2].

Przykłady

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

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

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

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

${\displaystyle a\uparrow \uparrow \uparrow b=a\uparrow ^{3}b}$

${\displaystyle a\uparrow \uparrow \uparrow \uparrow b=a\uparrow ^{4}b}$

${\displaystyle a\ \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow } _{n\ {\text{razy}}}\ b=a\uparrow ^{n}b}$

Konstrukcja

${\displaystyle a\uparrow ^{1}b=a\times a\times \ldots \times a}$

${\displaystyle a\uparrow ^{2}b=a\uparrow a\uparrow \ldots \uparrow a}$

${\displaystyle a\uparrow ^{3}b=a\uparrow \uparrow a\uparrow \uparrow \ldots \uparrow \uparrow a}$

${\displaystyle a\uparrow ^{4}b=a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow a}$

${\displaystyle a\uparrow ^{n}b=a\uparrow ^{n-1}a\uparrow ^{n-1}\dots \uparrow ^{n-1}a}$

gdzie ${\displaystyle a}$ występuje po prawej stronie równań zawsze dokładnie ${\displaystyle b}$ razy.

Inne przykłady

• ${\displaystyle a\uparrow 1=a^{1}=a.}$

${\displaystyle a\uparrow \uparrow 1=a\uparrow (a\uparrow \uparrow 0)=a\uparrow 1=a,}$

${\displaystyle a\uparrow ^{n+1}1=a\uparrow ^{n}(a\uparrow ^{n+1}0)=a\uparrow ^{n}1,}$

a stąd indukcyjnie uzasadniamy, że ${\displaystyle a\uparrow ^{n}1=a}$ dla wszystkich ${\displaystyle n\in \mathbb {N} .}$

• ${\displaystyle 2\uparrow 2=2^{2}=4,}$

${\displaystyle 2\uparrow \uparrow 2=2\uparrow (2\uparrow \uparrow 1)=2\uparrow 2=4,}$

${\displaystyle 2\uparrow ^{n+1}2=2\uparrow ^{n}(2\uparrow ^{n+1}1)=2\uparrow ^{n}2}$

i stąd indukcyjnie uzasadniamy, że ${\displaystyle 2\uparrow ^{n}2=4}$ dla wszystkich ${\displaystyle n\in \mathbb {N} .}$

Liczba Grahama

Osobny artykuł: Liczba Grahama.

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

Zobacz też

• Działanie dwuargumentowe
• Liczba Grahama
• Tetracja

Przypisy

1. Eric W.E.W. Weisstein Eric W.E.W., Knuth Up-Arrow Notation, [w:] MathWorld, Wolfram Research [dostęp 2016-05-14] (ang.).
2. FabioF. Caldarola FabioF. i inni, On the Arithmetic of Knuth’s Powers and Some Computational Results About Their Density, [w:] Yaroslav D.Y.D. Sergeyev, Dmitri E.D.E. Kvasov, Numerical Computations: Theory and Algorithms: Third International Conference, NUMTA 2019, Crotone, Italy, June 15–21, 2019, Revised Selected Papers, Part I, Springer Nature, 13 lutego 2020, s. 382, ISBN 978-3-030-39081-5 [dostęp 2023-03-08] (ang.).