Notarea puterilor iterate de Knuth
În matematică , notația puterilor iterate ale lui Knuth este o notație care face posibilă scrierea unor numere întregi foarte mari și care a fost introdusă de Donald Knuth în 1976. Ideea acestei notații se bazează pe conceptul de exponențiere repetată, în la fel cum exponențierea constă dintr-o înmulțire iterată sau înmulțirea unei adunări iterate.
Introducere
Iterează o funcție simplă
Iterația unei funcții simple este utilizată în aritmetică pentru a defini o operație mai complexă. Din funcția succesor , care face posibilă construirea unor numere întregi naturale prin incrementări succesive, adunarea este astfel definită ca o incrementare iterată:
la+b=la+1+1+⋯+1⏟ b copii ale 1{\ displaystyle {\ begin {matrix} a + b = a + \ underbrace {1 _ {} + 1+ \ dots +1} \\\ qquad \ quad \ \ b {\ mbox {copies of}} 1 \ end {matrice}}}Înmulțirea este definită ca o adăugire iterată:
la×b=la+la+⋯+la⏟ b copii ale la{\ displaystyle {\ begin {matrix} a \ times b = \ underbrace {a _ {} + a + \ dots + a} \\\ qquad \ quad \ \ b {\ mbox {copies of}} a \ end { matrice}}}În mod similar, exponențierea este definită ca o multiplicare iterată:
lab=la×la×⋯×la⏟ b copii ale la{\ displaystyle {\ begin {matrix} a ^ {b} = \ underbrace {a _ {} \ times a \ times \ dots \ times a} \\\ qquad \ b {\ mbox {copies of}} a \ end {matrice}}}
Generalizare
Pornind de la increment ca operație primitivă, iterațiile succesive fac posibilă definirea mai întâi a adunării, apoi a înmulțirii, apoi a exponențierii. Knuth dorea să generalizeze acest principiu; pentru aceasta a introdus o nouă notație pentru exponențiere, săgeata sus :
la↑b=lab{\ displaystyle a \ uparrow b = a ^ {b}}pe care îl poate generaliza astfel, folosind săgeata dublă în sus pentru exponențierea iterată - pe care o numește tetrare :
la↑↑b=la↑la↑⋯↑la⏟=lala...la b copii ale la{\ displaystyle {\ begin {matrix} a \ uparrow \ uparrow b = \ underbrace {a \ uparrow a \ uparrow \ cdots \ uparrow a} = a _ {} ^ {a ^ {{} ^ {. \, ^ { . \, ^ {. \, ^ {a}}}}}} \\\ \ \ b {\ mbox {copii ale}} a \ end {matrix}}}În conformitate cu această definiție, obținem:
3↑↑2=33=27{\ displaystyle 3 \ uparrow \ uparrow 2 = 3 ^ {3} = 27 \, \!}
3↑↑3=333=327=7625597484987{\ displaystyle 3 \ uparrow \ uparrow 3 = 3 ^ {3 ^ {3}} = 3 ^ {27} = 7 \, 625 \, 597 \, 484 \, 987 \, \!}
3↑↑4=3333=37625597484987{\ displaystyle 3 \ uparrow \ uparrow 4 = 3 ^ {3 ^ {3 ^ {3}}} = 3 ^ {7 \, 625 \, 597 \, 484 \, 987} \, \!}
3↑↑5=33333{\ displaystyle 3 \ uparrow \ uparrow 5 = 3 ^ {3 ^ {3 ^ {3 ^ {3}}}} \, \!}
etc.
Termenul este de formă și are cifre, adică mai mult decât cifre zecimale.
3↑↑4=3333{\ displaystyle 3 \ uparrow \ uparrow 4 = 3 ^ {3 ^ {3 ^ {3}}}}12580 ... 39387{\ displaystyle 12580 ... 39387}3638334640025{\ displaystyle 3 \, 638 \, 334 \, 640 \, 025}3,6×1012{\ displaystyle 3,6 \ times 10 ^ {12}}
Cu siguranță permite scrierea unor numere foarte mari, dar Knuth nu s-a oprit aici. El a continuat să definească operatorul săgeată triplă în sus , care este aplicația iterată a operatorului săgeată dublă în sus :
la↑↑↑b=la↑↑la↑↑⋯↑↑la⏟=la↑↑(la↑↑(⋯↑↑la))) b copii ale la{\ displaystyle {\ begin {matrix} a \ uparrow \ uparrow \ uparrow b = \ underbrace {a _ {} \ uparrow \ uparrow a \ uparrow \ uparrow \ dots \ uparrow \ uparrow a} = a _ {} \ uparrow \ uparrow (a \ uparrow \ uparrow (\ dots \ uparrow \ uparrow a))) \\\ qquad \ qquad \ \, b {\ mbox {copies of}} a \ end {matrix}}} (operații efectuate de la dreapta la stânga)
apoi a continuat cu operatorul săgeată cvadruplu :
la↑↑↑↑b=la↑↑↑la↑↑↑⋯↑↑↑la⏟b copii ale la{\ displaystyle {\ begin {matrix} a \ uparrow \ uparrow \ uparrow \ uparrow b = \ underbrace {a _ {} \ uparrow \ uparrow \ uparrow a \ uparrow \ uparrow \ uparrow \ dots \ uparrow \ uparrow \ uparrow a} \ \\ qquad \ qquad \ quad b {\ mbox {copii ale}} a \ end {matrix}}}Și așa mai departe. Regula generală afirmă că operatorul n -arrow este o succesiune de operatori ( n - 1) -arrows. Mai general,
b{\ displaystyle b}b{\ displaystyle b}
la ↑↑...↑⏟ b=la ↑...↑⏟ la ↑...↑⏟ la ... la ↑...↑⏟ la nu nu-1 nu-1 nu-1 ⏟ b copii ale la{\ displaystyle {\ 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 {copii ale}} a \ sfârșit {matrice}}}
Comutativitate
Exponențierea nu este comutativă : dacă a și b sunt diferite, este diferit de . Acesta este același pentru operatorii de mai jos: , , etc.
la↑b{\ displaystyle a \ uparrow b}b↑la{\ displaystyle b \ uparrow a}↑{\ displaystyle \ uparrow}↑↑{\ displaystyle \ uparrow \ uparrow}↑↑↑{\ displaystyle \ uparrow \ uparrow \ uparrow}
Paranteze și asociativitate
Chiar daca nu este scris între paranteze, calculele asociate dreptului de prioritate pentru fiecare operator , , etc.
↑{\ displaystyle \ uparrow}↑↑{\ displaystyle \ uparrow \ uparrow}↑↑↑{\ displaystyle \ uparrow \ uparrow \ uparrow}
Exemplu: =3↑2↑↑3↑4{\ displaystyle 3 \ uparrow 2 \ uparrow \ uparrow 3 \ uparrow 4}3↑(2↑↑(3↑4))){\ displaystyle 3 \ uparrow (2 \ uparrow \ uparrow (3 \ uparrow 4)))}
Acest lucru se datorează faptului că exponențierea nu este asociativă , prin urmare ordinea în care sunt efectuate operațiile este importantă. Deci (ie ) nu este (ie ). În cele de mai sus, operațiile sunt efectuate de la dreapta la stânga, cu alte cuvinte, parantezele sunt asociate de la dreapta la stânga.
3↑(2↑3){\ displaystyle 3 \ uparrow (2 \ uparrow 3)}3↑8=6561{\ displaystyle 3 \ uparrow 8 = 6 \, 561}(3↑2)↑3{\ displaystyle (3 \ uparrow 2) \ uparrow 3}9↑3=729{\ displaystyle 9 \ uparrow 3 = 729}
Rețineți că, în virtutea regulilor de putere, obținem = = . Dacă s-ar alege asocierea prioritară din stânga, acest lucru ar aduce al doilea operator de putere înapoi la o operație de multiplicare „simplă”. Creșterea unei puteri este mai puternică atunci când creștem termenul din dreapta (aceasta este la originea necomutativității):
(3↑2)↑3{\ displaystyle (3 \ uparrow 2) \ uparrow 3}(3↑2)×(3↑2)×(3↑2){\ displaystyle (3 \ uparrow 2) \ times (3 \ uparrow 2) \ times (3 \ uparrow 2)}3↑(2×3){\ displaystyle 3 \ uparrow (2 \ times 3)}
3↑(2↑3){\ displaystyle 3 \ uparrow (2 \ uparrow 3)}= = Este mai mare decât = = .
3↑(2×2×2){\ displaystyle 3 \ uparrow (2 \ times 2 \ times 2)}3↑8{\ displaystyle 3 \ uparrow 8}(3↑2)↑3{\ displaystyle (3 \ uparrow 2) \ uparrow 3}(3×3)↑3{\ displaystyle (3 \ times 3) \ uparrow 3}9↑3{\ displaystyle 9 \ uparrow 3}
Prin urmare, asociația este aleasă cu prioritate în dreapta; este singura alegere care produce o creștere demnă de un nou semn operativ.
Rezultatul lui va fi deci 6.561 și nu 729.
3↑2↑3{\ displaystyle 3 \ uparrow 2 \ uparrow 3}
Definiția puterilor iterate
Puterile iterate ale lui Knuth sunt definite formal după cum urmează:
la↑nub={labdacă nu=11 dacă b=0la↑nu-1(la↑nu(b-1))dacă nu {\ displaystyle a \ uparrow ^ {n} b = \ left \ {{\ begin {matrix} a ^ {b} \ qquad \ qquad \ qquad \ qquad && {\ mbox {si}} n = 1 \ quad \\ 1 \ qquad \ qquad \ qquad \ qquad \ && {\ mbox {si}} b = 0 \ quad \, \\ a \ uparrow ^ {n-1} (a \ uparrow ^ {n} (b-1)) && {\ mbox {altfel}} \ \, \ end {matrix}} \ right.}pentru toate numerele întregi a , b și n unde b ≥ 0 și n ≥ 1.
Această familie de funcții poate fi definită printr-un program iterativ:
function Knuth(rang: naturel; a, b: naturel) : naturel
begin
if rang = 1
then R = a^b
else begin
R := 1 (* 1 est élément neutre à droite pour l'exponentiation *)
(* Application b fois de l'opérateur à gauche "a Knuth(rang-1)" *)
for compteur := 1 to b do R := Knuth(rang-1, a, R)
end
return R
end.
sau printr-un program recursiv (în Haskell de exemplu):
(↑) :: Integer -> (Integer, Integer) -> Integer
a ↑ (1,b) = a^b
_ ↑ (_,0) = 1
a ↑ (n,b) = a ↑ (n-1,a ↑ (n,b-1))
Note despre notare
Într-o expresie a b , scriem exponentul b cu litere mari . Dar multe medii, cum ar fi limbajele de programare și e - mailurile cu text simplu, nu acceptă acest aranjament bidimensional. Prin urmare, au propus o notație liniară, a ** b pentru Fortran și a ↑ b pentru alte medii; săgeata îndreptată în sus sugerează ridicarea la o putere. Dacă setul de caractere nu conține o săgeată, se utilizează circumflexul ^ sau ambele asteriscuri ** .
O altă notație utilizată în acest articol este ↑ n pentru a indica un operator săgeată de ordinul n (unde ↑ 1 este echivalent cu ↑ singur).
După cum am spus mai sus, toți acești operatori (inclusiv exponențierea clasică a ↑ b ) nu sunt asociativi și, în absența parantezelor, trebuie asociați, de la dreapta la stânga, adică evaluarea se face de la dreapta la stânga pentru o expresie care conține cel puțin doi dintre acești operatori. De exemplu, a ↑ b ↑ c înseamnă a ↑ ( b ↑ c ), și nu ( a ↑ b ) ↑ c, care apoi ar fi scris a ↑ ( b × c ):
3↑↑3=3↑23=333 in valoare de 3(33)=327=7625597484987 si nu (33)3=273=3(3⋅3)=39=19683.{\ displaystyle 3 \ uparrow \ uparrow 3 = 3 \ uparrow ^ {2} 3 = 3 ^ {3 ^ {3}} {\ mbox {valorează}} 3 ^ {(3 ^ {3})} = 3 ^ {27} = 7 \, 625 \, 597 \, 484 \, 987 {\ text {și nu}} \ left (3 ^ {3} \ right) ^ {3} = 27 ^ {3} = 3 ^ { (3 \ cdot 3)} = 3 ^ {9} = 19 \, 683.}Există un motiv bun pentru alegerea acestei evaluări de la dreapta la stânga; într-adevăr, dacă alegerea ar fi fost de la stânga la dreapta, atunci un ↑↑ b ar fi însemnat un ↑ ( a ↑ ( b -1)) și ↑↑ nu ar fi fost un operator nou.
Generalizări ale notației lui Knuth
Unele numere sunt atât de mari încât notația săgeată a lui Knuth devine prea greoaie pentru a le descrie. Acesta este, de exemplu, cazul numărului Graham . The hyperopérateurs sau înlănțuite săgeată Conway poate fi folosit atunci.
la↑nub=hiper(la,nu+2,b)=la→b→nu(Knuth)(Conway){\ displaystyle {\ begin {matrix} a \ uparrow ^ {n} b && = && {\ mbox {hyper}} (a, n + 2, b) && = && a \ to b \ to n \\ {\ mbox {(Knuth)}} &&&&&&&&& {\ mbox {(Conway)}} \ end {matrix}}}Săgeata lui Knuth va fi utilizată pentru numere mici față de acestea, în timp ce săgețile înlănțuite sau hiperoperatorii vor fi potrivite pentru cele mai mari; atunci când aceste notații în sine devin insuficiente, așa cum este cazul de exemplu pentru secvențele Goodstein , este încă posibil să se utilizeze ierarhia creșterii rapide (care este aproximativ aceeași cu definirea notației , unde α este un număr ordinal ).
la↑αb{\ displaystyle a \ uparrow ^ {\ alpha} b}
Referințe
-
incrementul este procesul de adăugare a unui număr. De exemplu, într-o notație de numere întregi de către domino (sau pietricele mici), ar consta în adăugarea unui domino (sau a unei pietricele).1{\ displaystyle 1}
-
Continuare A014222 în Enciclopedia online a șirurilor întregi .
-
Omitem calificativul „sus”.
-
„Litera superioară” este termenul folosit în tipografie.
Bibliografie
linkuri externe
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">