Formule pentru numere prime

În matematică, căutarea unor formule exacte care să dea toate numerele prime, anumite familii de numere prime sau al n- lea număr prim s-a dovedit în general a fi în zadar, ceea ce a dus la satisfacerea cu formule aproximative. Această pagină listează principalele rezultate obținute.

Formule exacte simple

Speranța obținerii unei formule exacte și simple care să dea al n - lea număr prim $p n$ sau numărul $π ( n )$ al numerelor prime mai mici sau egale cu n , a întâlnit foarte devreme neregularitatea extremă a distribuției lor , ceea ce a dus la stabilirea pentru ținte mai puțin ambițioase. Dar chiar și căutarea formulelor care oferă doar numere prime se dovedește a fi destul de dezamăgitoare; astfel, este ușor de a arăta că nu există nici o funcție polinomială nu constantă $P ( n )$ , care ar lua doar primele valori pentru toate numere întregi $n$ , sau chiar aproape toate $Ns$ ; de fapt, nici nu știm dacă există un polinom de grad> 1 care ia o infinitate de valori prime.

Acest lucru explică interesul lui Euler remarca : a polinomului pătratic $P ( n ) = n 2 + n + 41$ este prim pentru toate numere întregi pozitive strict mai puțin de 40 (notă de faptul că și în cazul în care $n$ este un multiplu de 41, $P$ $($ $n$ $)$ de asemenea , va să fie multiplu de 41 și, prin urmare, să nu fie prim). Mai mult, 41 este cel mai mare „ număr Euler norocos ”, adică cel mai mare întreg $A$ pentru care polinomul $n$ $2$ $+$ $n$ $+$ $A$ este prim pentru toți $n$ strict mai mici decât $A$ $- 1$ ; aceasta rezultă din teorema Stark-Heegner , un rezultat al teoriei câmpului de clasă care nu a fost demonstrat până în 1967. În mod similar, alte formule polinomiale (de grad superior) produc secvențe de numere prime. Astfel, în 2010, unul dintre ei a făcut posibilă stabilirea unui nou record: o succesiune de 58 de numere prime: ${\ displaystyle P (40) = 1681 = 41 ^ {2}}$

{\ displaystyle {\ frac {1} {72}} n ^ {6} - {\ frac {5} {24}} n ^ {5} - {\ frac {1493} {72}} n ^ {4} + {\ frac {1027} {8}} n ^ {3} + {\ frac {100471} {18}} n ^ {2} - {\ frac {11971} {6}} n-57347}

este prim pentru fiecare număr întreg

n de

la –42 la 15.

Au fost luate în considerare alte formule care utilizează funcții mai generale, precum cea a lui Mersenne , cea mai faimoasă fiind cea conjecturată de Fermat : $F n = 2 2 n + 1$ este prim pentru toate $n$ . Din păcate, dacă aceste numere (numite în continuare numere Fermat ) sunt într-adevăr prime pentru $0 \leq n \leq 4$ , Euler a descoperit că al șaselea, $F 5$ , este divizibil cu 641, distrugând conjectura; în prezent, credem dimpotrivă că $F n$ este întotdeauna compus imediat ce $n > 4$ . În același gen, formula lui Mills generează doar numere prime, dar are dezavantajul de a fi doar teoretică.

Formule aproximative

Formule aproximative pentru $p n$ sau $π ( n )$ au fost concepute până în secolul al XVIII- lea, culminând cu conjectura lui Legendre și Gauss . Dacă cea mai simplă ipoteză a lor a fost demonstrată de Hadamard și La Vallée Poussin un secol mai târziu (este teorema numărului prim ), dificultatea problemei este bine arătată de faptul că una dintre conjecturile lui Gauss, mai precisă și care limitează $π ($ $n$ $)$ prin , care părea foarte plauzibilă având în vedere tabelele acestor două funcții , s-a dovedit totuși fals, dar numai pentru valorile gigantice ale lui $n$ . ${\ displaystyle \ lim _ {n \ to + \ infty} \ pi (n) \ ln n / n = 1,}$ ${\ displaystyle {\ rm {Li}} (n) = \ int _ {2} ^ {n} {\ frac {\ mathrm {d} x} {\ ln x}}}$

Rezultate mai precise și, în special, o estimare bună a termenului de eroare $h ( n )$ din formula $p n = n ln n + h ( n )$ , sunt încă supuse unor conjecturi (adesea în funcție de presupunerea lui Riemann ); printre cele mai bune rezultate cu adevărat demonstrate, putem cita următorul cadru, stabilit de Dusart în 1999:

{\ displaystyle n \ left (\ ln n + \ ln \ ln n-1 \ right) <p_ {n} <n \ left (\ ln n + \ ln \ ln n-1/2 \ right).}

Aceste metode sunt departe de a oferi formule exacte; de exemplu, acest cadru afirmă doar că numărul milenar prim, 7919, este cuprins între 7840 și 8341.

Formule exacte fără interes practic

În ciuda observațiilor precedente, este totuși posibil să se obțină formule exacte de aspect simplu, dar fără interes practic din cauza calculelor prea lungi.

Utilizarea teoremei lui Wilson

Teorema lui Wilson îl face ușor pentru a arăta că funcția $f ( n ) = 2 + (2 ( n ) mod (? N + 1))$ produce toate numerele prime, și numai ei, atunci când $n$ trece prin toate numere întregi pozitive: $f ( n ) = n + 1$ dacă n + 1 este prim, iar $f ( n ) = 2 în$ caz contrar.

Factorialul de $n$ rapid ia valori mult prea mari pentru a fi utilizabil în practică, dar utilizarea funcției modulo (care știm cum să calculeze rapid) dejoacă această dificultate; cu toate acestea, singurele metode cunoscute pentru a calcula $f ( n )$ iau aproximativ $n$ operații elementare, în plus, această funcție nu dă de fapt $π ( n )$ , ci doar testează dacă $n$ este prim sau nu; pentru acest test, sau pentru a calcula $π ( n )$ , $f$ este, prin urmare, mult mai ineficient decât metoda de împărțire cu toți numerele mai mici sau egale cu $\sqrt n$ (sau decât sita lui Eratostene ), metode în sine mult mai lente decât cele mai bune din prezent teste de primalitate cunoscute.

Alte formule care dau direct $p n$ sau $π ( n )$ pot fi construite din $f$ ; astfel, avem, folosind funcția de număr întreg $⌊ ∙ ⌋$ :

{\ displaystyle \ pi (m) = \ sum _ {j = 2} ^ {m} \ left \ lfloor {(j-1)! + 1 \ over j} - \ left \ lfloor {(j-1)! \ over j} \ right \ rfloor \ right \ rfloor}

;

dar aceste formule sunt chiar mai puțin ușor de utilizat decât cea care dă $f$ .

Simularea sitei Eratostene

O altă abordare, mai promițătoare și care nu folosește teorema lui Wilson, constă în esență în simularea sitei Eratostene sau a formulelor care pot fi deduse din aceasta, cum ar fi formula de includere-excludere a lui Legendre; este terenul preferat al multor amatori, astfel, următoarele formule au fost stabilite în 2000 de către un profesor de spaniolă, SM Ruiz:

{\ displaystyle \ pi (k) = k-1 + \ sum _ {j = 2} ^ {k} \ left [{2 \ over j} \ left (1+ \ sum _ {s = 1} ^ {\ left \ lfloor {\ sqrt {j}} \ right \ rfloor} \ left (\ left \ lfloor {j-1 \ over s} \ right \ rfloor - \ left \ lfloor {j \ over s} \ right \ rfloor \ dreapta) \ dreapta) \ dreapta]}

și

{\ displaystyle p_ {n} = 1 + \ sum _ {k = 1} ^ {2 (\ lfloor n \ ln (n) \ rfloor +1)} \ left (1- \ left \ lfloor {\ pi (k ) \ over n} \ right \ rfloor \ right).}

Rețineți numărul mare de însumări din aceste formule, ceea ce înseamnă că și ele nu ar fi foarte utile în practică; metodele mult mai bune de calcul exact ale $π ( n )$ și $p n$ , pe care le vom găsi detaliate în articolul dedicat acestor funcții , rămân relativ ineficiente.

Relație diofantină

Luând în considerare observațiile primei secțiuni, existența unor polinoame cu mai multe variabile care iau doar valori prime părea puțin probabilă. De asemenea, lucrarea lui Matiyasevich care a rezolvat în 1970 a zecea problemă a lui Hilbert arătând că orice relație diofantină ar putea fi codificată de un astfel de polinom, a provocat o adevărată surpriză. Este chiar posibil să se dea exemple explicite ale acestui rezultat; astfel, următorul polinom monstruos (de grad 25 și cuprinzând 26 de variabile):

{\ displaystyle (k + 2) (1- \ alpha _ {0} ^ {2} - \ alpha _ {1} ^ {2} - \ cdots - \ alpha _ {13} ^ {2})}

{\ displaystyle \ alpha _ {0} = wz + h + jq}

{\ displaystyle \ alpha _ {1} = (gk + 2g + k + 1) (h + j) + hz}

{\ displaystyle \ alpha _ {2} = 16 (k + 1) ^ {3} (k + 2) (n + 1) ^ {2} + 1-f ^ {2}}

{\ displaystyle \ alpha _ {3} = 2n + p + q + ze}

{\ displaystyle \ alpha _ {4} = e ^ {3} (e + 2) (a + 1) ^ {2} + 1-o ^ {2}}

{\ displaystyle \ alpha _ {5} = (a ^ {2} -1) y ^ {2} + 1-x ^ {2}}

{\ displaystyle \ alpha _ {6} = 16r ^ {2} y ^ {4} (a ^ {2} -1) + 1-u ^ {2}}

{\ displaystyle \ alpha _ {7} = n + l + vy}

{\ displaystyle \ alpha _ {8} = (a ^ {2} -1) l ^ {2} + 1-m ^ {2}}

{\ displaystyle \ alpha _ {9} = ai + k + 1-li}

{\ displaystyle \ alpha _ {10} = [(a + u ^ {2} (u ^ {2} -a)) ^ {2} -1] (n + 4dy) ^ {2} + 1- (x + cu) ^ {2}}

{\ displaystyle \ alpha _ {11} = p + l (an-1) + b (2an + 2a-n ^ {2} -2n-2) -m}

{\ displaystyle \ alpha _ {12} = q + y (ap-1) + s (2ap + 2a-p ^ {2} -2p-2) -x}

{\ displaystyle \ alpha _ {13} = z + pl (ap) + t (2ap-p ^ {2} -1) -pm}

a, pentru un set de valori strict pozitive (când ), exact mulțimea numerelor prime. ${\ displaystyle (a, \ dots, z) \ in \ mathbb {N} ^ {26}}$

Dar ne putem întreba dacă este cu adevărat aici din nou o „formulă”. De asemenea, este extrem de dificil să găsești un set de 26 de variabile care să dea un număr pozitiv și nu există o metodă cunoscută pentru rezolvarea unui astfel de sistem decât prin explorarea tuturor combinațiilor posibile ale parametrilor.

Secvențe definite prin inducție

Deși nu putem vorbi exact despre o formulă, o secvență definită printr-o relație de forma $u n +1 = f ( u n )$ , unde $f$ este o funcție destul de simplă și care ar lua doar valori prime, ar rămâne interesantă. Anumite secvențe derivate din dovada lui Euclid a infinității numerelor prime (cum ar fi secvența lui Sylvester ) se dovedește a fi dezamăgitoare în acest sens, așa că nu știm nici măcar dacă există o infinitate de numere primare primare . Știm de fapt doar câteva exemple interesante ale unor astfel de secvențe, în plus, de o formă oarecum mai complexă.

Algoritmul FRACTRAN

Conway a definit astfel o generalizare a problemei Syracuse , care o transformă într-un limbaj de programare, FRACTRAN ; următorul text:

{\ frac {17} {91}}, {\ frac {78} {85}}, {\ frac {19} {51}}, {\ frac {23} {38}}, {\ frac {29} {33}}, {\ frac {77} {29}}, {\ frac {95} {23}}, {\ frac {77} {19}}, {\ frac {1} {17}}, { \ frac {11} {13}}, {\ frac {13} {11}}, {\ frac {15} {14}}, {\ frac {15} {2}}, {\ frac {55} { 1}}.

corespunde, pentru acest limbaj, unui program care produce, în ordine, succesiunea numerelor prime (o putem interpreta deci ca o secvență definită prin inducție); eficacitatea acestui program fiind extrem de slabă, interesul este doar în eleganța scrierii sale.

Suita Rowland

Secvența $u n$ definită de relația de recurență

{\ displaystyle a_ {n} = a_ {n-1} + \ operatorname {gcd} (n, a_ {n-1}), \ quad a_ {1} = 7,}

(unde $mcd ( x , y )$ denotă MCD de $x$ și $y$ ) și $u n = a n +1 - a n$ începe cu 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3 , 1, 1, ... (continuare A132199 a OEIS ). Rowland a demonstrat în 2008 că această secvență conține (în afară de 1) numai numere prime.

Secvențe în funcție de un număr real Formula Mills

În 1947, William H. Mills a arătat că există numere reale $M$ astfel încât pentru orice număr întreg $n$ , partea întreagă a lui $M (3 n )$ este un număr prim. Cel mai mic $M$ care are această proprietate, constanta Mills , este, de asemenea, cunoscut cu o bună precizie, dar care se dovedește a fi la fel de iluzoriu pentru calcularea numerelor prime mari, de exemplu, deoarece dimensiunea lui $p ( n ) = ⌊ M (3 n ) ⌋$ devine rapid mult mai mare decât orice poate păstra un computer (pentru a stoca $p (25)$ , aveți deja nevoie de un terabyte ).

Suită Fridman

În 2017, Fridman și colab. au arătat că secvența de reali $( f n )$ definită de:

${\ displaystyle f_ {1} = \ sum _ {k = 1} ^ {\ infty} {\ frac {p_ {k} -1} {p_ {k-1} \ #}} = \ sum _ {k = 1} ^ {\ infty} {\ frac {p_ {k} -1} {\ prod _ {i = 1} ^ {k-1} p_ {i}}}}$
${\ displaystyle \ forall n \ geq 1 \ quad f_ {n + 1} = \ lfloor f_ {n} \ rfloor \ left (f_ {n} - \ lfloor f_ {n} \ rfloor +1 \ right)}$

verificat:

{\ displaystyle \ forall n \ geq 1 \ quad p_ {n} = \ lfloor f_ {n} \ rfloor}

Irațional $f 1 = 2.9200509773 ...$ nu este altul decât valoarea medie a secvenței 2, 3, 2, 3, 2, 5, etc. al cărui al $n-$ lea termen este cel mai mic număr prim care nu împarte $n$ .

Deși calculele corespunzătoare sunt mai ușor de gestionat decât cele din formula lui Mills, acest rezultat rămâne la fel de teoretic. Într-adevăr, aceste calcule necesită cunoașterea unui număr tot mai mare de zecimale de $f 1$ (aproximativ $n$ zecimale pentru a obține $p n$ ) , dar pentru a obține $n$ zecimale ale lui $f 1$ , trebuie să cunoaștem deja valorile primelor $n$ numere prime . Pe de altă parte, aceasta oferă compresie de memorie , de fapt, stocarea zecimalelor necesită mai puțină memorie decât pentru primele numere prime. $nu$ $nu$

Fracție continuă

Conceptul de fracție continuă utilizat pentru a defini numărul real pozitiv A064442 din care vom găsi secvența de numere prime utilizând următoarea recurența: . Rezultă că . ${\ displaystyle u_ {1} = [p_ {1}, p_ {2}, p_ {3}, ...] = 2.31303673643 ...}$ ${\ displaystyle u_ {n + 1} = (u_ {n} - \ lfloor u_ {n} \ rfloor) ^ {- 1}}$ ${\ displaystyle p_ {n} = \ lfloor u_ {n} \ rfloor}$

Metoda lui Fridman și colab. poate fi văzut ca o alternativă la metoda fracției continue (cunoscută anterior) și, prin urmare, putem face aceeași rezervă: numărul este definit (mai sus) folosind numere prime, deci avem nevoie de o definiție alternativă independentă de numere mai întâi pentru această metodă fii utilizabil . ${\ displaystyle u_ {1}}$

Note și referințe

(fr) Acest articol este preluat parțial sau în întregime din articolul Wikipedia din limba engleză intitulat „ Formula for primes ” ( vezi lista autorilor ) .

GH Hardy și EM Wright ( tradus din engleză de F. Sauvageot), Introducere în teoria numerelor [„ O introducere în teoria numerelor ”], Vuibert - Springer ,2007, p. 23, a. 21, datorită Goldbach ( Scrisoarea CLI , către Euler , 18 noiembrie 1752). Pentru o generalizare, a se vedea, de asemenea, teorema 22, p. 24 și 83, datorită (în) Morgan Ward (în) , „ O generalizare a unei teoreme familiare referitoare la numere prime ” , J. London Math. Soc. , vol. 5,1930, p. 106-107.
(în) Andrew Granville , Conferința la MAA, decembrie 2008 , în care sunt trasate multe observații informale ale acestui articol; aici este înregistrarea (audio) ; se presupune totuși că, de exemplu, acesta este cazul polinomului $n 2 + 1$ , iar conjectura Bateman-Horn prezice comportamentul acestor valori prime într-un mod bine confirmat empiric.
David Larousserie, „ Continuare record nouă pentru numerele prime ” , pe Sciences et Avenir ,23 septembrie 2010(accesat la 4 mai 2018 ) .
Acestea sunt de fapt numere prime în Z , adică numere întregi relative a căror valoare absolută este un număr prim.
Boklan și Conway au publicat în mai 2016 o analiză foarte fină care estimează probabilitatea ca un alt număr prim să fie mai mic decât unul dintr-un miliard ( (ro) Boklan și Conway, „ Așteptați cel mult o miliardime dintr-un nou Fermat Prime! ” , Matematică Intelligencer. , Springer,2016( arXiv 1605.01371v1 )).
A se vedea Numărul de skewes , unde se vor găsi și cele mai bune valori ale acestor n cunoscute în prezent.
(în) Pierre Dusart, " A k- a primă este mai mare decât k (ln ln ln k + k-1) pentru k ≥2 " , Matematica calculului , vol. 68,1999, p. 411–415 ( citește online ) ; coaching-ul este valabil pentru n > 4 cu Convenția și, de fapt, acest articol oferă terminalului un pic mai precis, dar valabil doar pentru $n$ suficient de mare: avem (pentru $n$ $> 40000$ ) pentru suta mielea prime , acest lucru corespunde încadrarea . ${\ displaystyle p_ {2} = 2}$ ${\ displaystyle n (\ ln n + \ ln \ ln n-1) <p_ {n} <n (\ ln n + \ ln \ ln n-0,95);}$ ${\ displaystyle p_ {100000} = 1 \, 299 \, 709}$ ${\ displaystyle 1 \, 295 \, 639 <p_ {100000} <1 \, 300 \, 639}$
Într-adevăr, dacă n + 1 este prim, conform teoremei lui Wilson, avem $n !$ congruent la –1 modulul $n + 1$ , deci împărțirea $2 ( n !)$ la $n + 1$ lasă restul lui n - 1 și f ( n ) = 2 + ( n - 1) = n + 1 în acest caz; dacă n + 1 este compus și strict mai mare decât 4, n ! este divizibil cu n + 1 și $f ( n ) = 2 + 0 = 2$ ; în cele din urmă, $f (0) = 2$ și $f (3) = 2$ .
Această formulă (cunoscută și sub numele de formula sită ) a fost determinată de Legendre pentru a calcula rapid $π ( n )$ fără a fi nevoie să caute în mod explicit toate numerele prime mai mici decât $n$ ; o vom găsi, precum și îmbunătățirile sale mai recente, în articolul dedicat lui $π ( n )$ .
Aceste formule apar pe pagina personală a autorului lor, Sebastián Martín Ruiz (es) ; a publicat o demonstrație în 2002 (în) , în colaborare cu S. Sondow.
(en) primes.utm.edu Calcul condițional al pi (10 ^ 24).
Astfel, în 2016 putem determina doar exact $π (10 24 )$ , în timp ce știm cum să testăm dacă un număr de ordinul 10 200 este prim în câteva minute.
Matiyasevich a arătat în 1999 că putem reduce orice polinom care codifică astfel o relație diofantină cu un polinom în 9 variabile, dar cu prețul, în acest exemplu, al unui grad care depășește 10 45 . În schimb, am determinat un polinom de gradul 4, dar cu 56 de variabile; vezi despre (în) James P. Jones , „ Ecuația diofantină universală ” , J. Symb. Logică , vol. 47, n o 3,1982, p. 549–571 ( DOI 10.2307 / 2273588 ).
(în) James P. Jones , Daihachiro Sato (în) , Hideo Wada și Douglas Wiens (în) , „ Reprezentarea diofantină a setului de numere prime ” , Amer. Matematica. Lunar , vol. 83, nr . 6,1976, p. 449-464 ( citește online )( Premiul Lester Randolph Ford 1977).
(în) Eric S. Rowland , A Natural Prime-Generating Recurrence , voi. 11, Journal of Integer Sequences,2008, 08.2.8 p. ( Bibcode 2008JIntS..11 ... 28R , arXiv 0710.3217 , citiți online )
(în) William H. Mills, „ A prime Representing function ” , Bull. Amar. Matematica. Soc. ,1947, p. 604 și 1196 ( citiți online ).
(en) D. Fridman, J. Garbulsky, B. Glecer, J. Grime și MT Florentin, „ O constantă prim-reprezentativă ” , Amer. Matematica. Lună. , vol. 126, nr . 1,ianuarie 2019, p. 70-72 ( DOI 10.1080 / 00029890.2019.1530554 , citiți online ).
Suite A249270 din OEIS .
(în) Steven R. Finch, Constantele matematice , vol. II, Cambridge University Press,2018( citiți online ) , p. 171.
Suite A053669 de la OEIS: „ Primul cel mai mic care nu împarte n ” .

Vezi și tu

Bibliografie

Jean-Paul Delahaye , Numere prime minunate: Călătorie către inima aritmeticii ,2000[ detaliul ediției ]
Marcus du Sautoy ( traducere din engleză), La Symphonie des numbers primes , Paris, ediții Héloïse d'Ormesson,2005, 491 p. ( ISBN 2-35087-011-1 )

Link extern

(ro) Eric W. Weisstein , „ Prime Formulas ” , pe MathWorld