Formule per i numeri primi

In matematica, la ricerca di formule esatte dando tutti i numeri primi, alcune famiglie di numeri primi o il n- esimo numero primo è generalmente dimostrato di essere vana, che ha portato ad essere soddisfatto con le formule approssimate. Questa pagina elenca i principali risultati ottenuti.

Formule esatte semplici

La speranza di ottenere una formula esatta e semplice dando l' ennesima numero primo $p n$ , o il numero di $π ( n )$ di numeri primi inferiore o uguale a n , molto presto incontrato l'estrema irregolarità della loro distribuzione , che ha portato al contenuto con obiettivi meno ambiziosi. Ma anche la ricerca di formule che forniscano solo numeri primi risulta essere piuttosto deludente; quindi, è facile mostrare che non esiste una funzione polinomiale non costante $P ( n )$ che prenderebbe solo i primi valori per tutti gli interi $n$ , o anche quasi tutti gli $n$ ; infatti, non sappiamo nemmeno se esiste un polinomio di grado> 1 che assume un'infinità di valori primi.

Questo spiega l'interesse dell'osservazione di Eulero : il polinomio quadratico $P ( n ) = n 2 + n + 41$ è primo per tutti gli interi positivi strettamente inferiori a 40 (si noti che e se $n$ è un multiplo di 41, $P$ $($ $n$ $)$ sarà anche essere un multiplo di 41, e quindi non primo). Inoltre, 41 è il più grande “ numero di Eulero fortunato ”, cioè il più grande intero $A$ per cui il polinomio $n$ $2$ $+$ $n$ $+$ $A$ è primo per tutti gli $n$ strettamente minori di $A$ $- 1$ ; questo deriva dal teorema di Stark-Heegner , un risultato della teoria dei campi di classe che non fu dimostrata fino al 1967. Allo stesso modo, altre formule polinomiali (di grado superiore) producono sequenze di numeri primi. Così, nel 2010, uno di loro ha permesso di stabilire un nuovo record: una sequenza di 58 numeri primi: ${\ 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}

è primo per ogni numero intero

n

compreso tra –42 e 15.

Sono state prese in considerazione altre formule che utilizzano funzioni più generali, come quella di Mersenne , la più famosa è quella ipotizzata da Fermat : $F n = 2 2 n + 1$ è primo per ogni $n$ . Sfortunatamente, se questi numeri (d'ora in poi chiamati numeri di Fermat ) sono davvero primi per $0 \leq n \leq 4$ , Eulero scoprì che il sesto, $F 5$ , è divisibile per 641, rovinando la congettura; attualmente si pensa al contrario che $F n$ sia sempre composto non appena $n > 4$ . Allo stesso modo, la formula di Mills genera solo numeri primi, ma ha lo svantaggio di essere solo teorica.

Formule approssimative

Formule approssimate per $p n$ o $π ( n )$ sono stati ideati al XVIII ° secolo, che si conclude con la congettura di Legendre e Gauss . Se la loro ipotesi più semplice fu dimostrata da Hadamard e La Vallée Poussin un secolo dopo (è il teorema dei numeri primi ), la difficoltà del problema è ben dimostrata dal fatto che una delle congetture di Gauss, più precisa, e che delimita $π ($ $n$ $)$ by , che sembrava molto plausibile alla luce delle tabelle di queste due funzioni , si è però rivelato falso, ma solo per valori giganteschi di $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}}}$

Risultati più precisi, ed in particolare una buona stima del termine di errore $h ( n )$ nella formula $p n = n ln n + h ( n )$ , sono ancora soggetti a congetture (spesso dipendenti dall'ipotesi di Riemann ); tra i migliori risultati realmente dimostrati, possiamo citare il seguente framework, determinato da Dusart nel 1999:

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

Questi metodi sono lontani dal fornire formule esatte; ad esempio, questo frame afferma solo che il millesimo numero primo, 7919, è compreso tra 7840 e 8341.

Formule esatte senza interesse pratico

Nonostante le considerazioni precedenti, è comunque possibile ottenere formule esatte di semplice apparenza, ma senza interesse pratico a causa di calcoli troppo lunghi.

Uso del teorema di Wilson

Il teorema di Wilson rende facile mostrare che la funzione $f ( n ) = 2 + (2 ( n ) mod (? N + 1))$ produce tutti i numeri primi, e solo loro, quando $n$ attraversa tutti gli interi positivi: $f ( n ) = n + 1$ se n + 1 è primo e $f ( n ) = 2$ altrimenti.

Il fattoriale di $n$ assume rapidamente valori troppo grandi per essere utilizzabili in pratica, ma l'uso della funzione modulo (che sappiamo calcolare velocemente) aggira questa difficoltà; tuttavia, gli unici metodi noti per calcolare $f ( n )$ richiedono circa $n$ operazioni elementari, inoltre, questa funzione non fornisce effettivamente $π ( n )$ , ma verifica solo se $n$ è primo oppure no; per questo test, o per calcolare $π ( n )$ , $f$ è quindi molto più inefficiente del metodo di divisione per tutti gli interi minori o uguali a $\sqrt n$ (o del setaccio di Eratostene ), metodi a loro volta molto più lenti dei migliori attualmente test di primalità noti.

Altre formule che danno direttamente $p n$ o $π ( n )$ possono essere costruite da $f$ ; quindi, usando la funzione intera $⌊ ∙ ⌋, abbiamo$ :

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

;

ma queste formule sono ancora meno facili da usare di quella che dà $f$ .

Simulazione del setaccio di Eratostene

Un altro approccio, più promettente e che non utilizza il teorema di Wilson, consiste essenzialmente nel simulare il setaccio di Eratostene , o le formule che se ne possono dedurre, come la formula di inclusione-esclusione di Legendre; è il terreno preferito di molti dilettanti, quindi le seguenti formule sono state stabilite nel 2000 da un insegnante di spagnolo, 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 \ destra) \ destra) \ destra]}

{\ 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).}

Notare il gran numero di somme in queste formule, il che significa che anch'esse non sarebbero molto utili nella pratica; molto migliori metodi di calcolo esatto di $π ( n )$ e $p n$ , che troveremo dettagliato nel l'articolo dedicato a queste funzioni , rimangono relativamente inefficiente.

Relazione diofantina

Tenendo conto delle osservazioni della prima sezione, l'esistenza di polinomi con diverse variabili che assumevano solo valori primi sembrava improbabile. Inoltre, il lavoro di Matiyasevich che ha risolto nel 1970 il decimo problema di Hilbert mostrando che qualsiasi relazione diofantina poteva essere codificata da un tale polinomio, ha causato una vera sorpresa. È anche possibile fornire esempi espliciti di questo risultato; quindi, il seguente mostruoso polinomio (di grado 25 e comprendente 26 variabili):

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

con

{\ 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, per un insieme di valori strettamente positivi (quando ), esattamente l'insieme dei numeri primi. ${\ displaystyle (a, \ dots, z) \ in \ mathbb {N} ^ {26}}$

Ma ci si può comunque chiedere se sia davvero qui di nuovo una "formula". È anche estremamente difficile trovare un insieme di 26 variabili che danno un numero positivo e non esiste un metodo noto per risolvere un tale sistema se non esplorando tutte le possibili combinazioni dei parametri.

Sequenze definite dall'induzione

Sebbene non si possa parlare esattamente di una formula, una sequenza definita da una relazione della forma $u n +1 = f ( u n )$ , dove $f$ è una funzione abbastanza semplice, e che prenderebbe solo valori primi, rimarrebbe interessante. Alcune sequenze derivate dalla dimostrazione di Euclide dell'infinità dei numeri primi ( come la sequenza di Silvestro ) si dimostrano deludenti sotto questo aspetto, quindi non sappiamo nemmeno se esiste un'infinità di numeri primi primoriali . Conosciamo infatti solo alcuni interessanti esempi di tali sequenze, per di più di forma un po 'più complessa.

Algoritmo FRACTRAN

Conway ha così definito una generalizzazione del problema Syracuse , che lo trasforma in un linguaggio di programmazione, FRACTRAN ; il testo seguente:

{\ 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}}.

corrisponde, per questo linguaggio, ad un programma che produce, in ordine, la sequenza di numeri primi (possiamo quindi interpretarla come una sequenza definita per induzione); essendo l'efficacia di questo programma estremamente debole, l'interesse è solo nell'eleganza della sua scrittura.

Rowland's Suite

La sequenza $u n$ definita dalla relazione di ricorrenza

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

(dove $gcd ( x , y )$ indica il GCD di $x$ ed $y$ ) ed $u n = a n + 1 - un n$ inizia con 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3 , 1, 1, ... (seguito A132199 del OEIS ). Rowland ha dimostrato nel 2008 che questa sequenza contiene (a parte 1) solo numeri primi.

Sequenze dipendenti da un numero reale Formula Mills

Nel 1947, William H. Mills dimostrò che esistono numeri reali $M$ tali che per ogni intero $n$ , la parte intera di $M (3 n )$ è un numero primo. La più piccola $M$ avente questa proprietà, la costante di Mills , è anche conosciuta con buona precisione, ma che risulta essere altrettanto illusoria per il calcolo di numeri primi grandi, ad esempio perché la dimensione di $p ( n ) = ⌊ M (3 n ) ⌋$ diventa rapidamente molto più grande di qualsiasi cosa un computer possa contenere (per memorizzare $p (25)$ , hai già bisogno di un terabyte ).

Fridman Suite

Nel 2017, Fridman et al. hanno dimostrato che la sequenza di reali $( f n )$ definita da:

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

controllato:

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

L' irrazionale $f 1 = 2.9200509773\dots$ non è altro che il valore medio della sequenza 2, 3, 2, 3, 2, 5, ecc. il cui $n-$ esimo termine è il numero primo più piccolo che non divide $n$ .

Sebbene i calcoli corrispondenti siano più gestibili di quelli della formula di Mills, questo risultato rimane altrettanto teorico. Infatti, questi calcoli richiedono di conoscere un numero crescente di cifre decimali di $f 1$ (circa $n$ decimali per ottenere $p n$ ) , ma per ottenere $n$ decimali di $f 1$ , dobbiamo già conoscere i valori dei primi $n$ numeri primi . D'altra parte, questo fornisce la compressione della memoria , infatti, la memorizzazione dei decimali richiede meno memoria rispetto ai primi numeri primi. $non$ $non$

Frazione continua

Il concetto di frazione continua utilizzata per definire il numero reale positivo A064442 da cui troviamo la sequenza dei numeri primi utilizzando la seguente ricorrenza: . Ne consegue che . ${\ 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}$

Il metodo di Fridman et al. può essere visto come un'alternativa al metodo della frazione continua (noto in precedenza), e possiamo quindi fare la stessa prenotazione: il numero è definito (sopra) utilizzando numeri primi, quindi abbiamo bisogno di una definizione alternativa indipendente dai numeri prima per questo metodo essere utilizzabile . ${\ displaystyle u_ {1}}$

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Formula for prime " ( vedere l'elenco degli autori ) .

GH Hardy e EM Wright ( tradotto dall'inglese da F. Sauvageot), Introduzione alla teoria dei numeri [" Un'introduzione alla teoria dei numeri "], Vuibert - Springer ,2007, p. 23, th. 21, a causa di Goldbach ( Lettera CLI , a Euler , 18 novembre 1752). Per una generalizzazione, vedere anche Teorema 22, p. 24 e 83, a causa di (in) Morgan Ward (in) , " Una generalizzazione di un teorema familiare riguardante i numeri primi " , J. London Math. Soc. , vol. 5,1930, p. 106-107.
(in) Andrew Granville , Conferenza al MAA, dicembre 2008 , da cui sono tratte molte osservazioni informali di questo articolo; ecco la registrazione (audio) ; si ipotizza tuttavia che, ad esempio, questo sia il caso del polinomio $n 2 + 1$ , e la congettura di Bateman-Horn prevede il comportamento di questi valori primi in modo ben confermato empiricamente.
David Larousserie, " New record continuation for prime numbers " , on Sciences et Avenir ,23 settembre 2010(accesso 4 maggio 2018 ) .
Questi sono infatti numeri primi in Z , cioè interi relativi il cui valore assoluto è un numero primo.
Boklan e Conway hanno pubblicato nel maggio 2016 un'analisi molto raffinata che stima la probabilità che un altro numero primo sia inferiore a uno su un miliardo ( (en) Boklan e Conway, " Aspettatevi al massimo un miliardesimo di un nuovo Fermat Prime! " , Matematica Intelligencer. , Springer,2016( arXiv 1605.01371v1 )).
Vedi Number of Skewes , dove si troveranno anche i migliori valori di questi n attualmente conosciuti.
(in) Pierre Dusart, " Il k- esimo premio è maggiore di k (ln ln ln k + k-1) per k ≥2 " , Matematica del calcolo , Vol. 68,1999, p. 411–415 ( leggi in linea ) ; il coaching è valido per n > 4 con la Convenzione e infatti questo articolo dà il terminale un po 'più preciso, ma valido solo per $n$ abbastanza grandi: abbiamo (per $n$ $> 40000$ ) per il centomillesimo primo,, questo corrisponde a l'inquadratura . ${\ 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}$
Infatti, se n + 1 è primo, secondo il teorema di Wilson, abbiamo $n !$ congruente a –1 modulo $n + 1$ , quindi dividendo $2 ( n !)$ per $n + 1 si$ ottiene un resto di n - 1 ef ( n ) = 2 + ( n - 1) = n + 1 in questo caso; se n + 1 è composto e strettamente maggiore di 4, n ! è divisibile per n + 1 e $f ( n ) = 2 + 0 = 2$ ; infine, $f (0) = 2$ ed $f (3) = 2$ .
Questa formula (nota anche come formula del setaccio ) è stata determinata da Legendre per calcolare rapidamente $π ( n )$ senza la necessità di cercare esplicitamente tutti i numeri primi inferiori a $n$ ; lo troverete, così come i suoi miglioramenti più recenti, nell'articolo dedicato a $π ( n )$ .
Queste formule appaiono sulla pagina personale del loro autore, Sebastián Martín Ruiz (es) ; ha pubblicato una dimostrazione nel 2002 (in) , in collaborazione con S. Sondow.
(en) primes.utm.edu Calcolo condizionale di pi greco (10 ^ 24).
Quindi, nel 2016 siamo solo in grado di determinare esattamente $π (10 24 )$ , mentre sappiamo come verificare se un numero dell'ordine di 10 200 è primo in pochi minuti.
Matiyasevich ha mostrato nel 1999 che possiamo ridurre qualsiasi polinomio codificando così una relazione diofantina a un polinomio in 9 variabili, ma al costo, in questo esempio, di un grado superiore a 10 45 . Al contrario, abbiamo determinato un polinomio di grado 4, ma con 56 variabili; vedere su (in) James P. Jones , " Universal diophantine equation " , J. Symb. Logica , vol. 47, n o 3,1982, p. 549–571 ( DOI 10.2307 / 2273588 ).
(dentro) James P. Jones , Daihachiro Sato (dentro) , Hideo Wada e Douglas Wiens (dentro) , " Rappresentazione diofantina dell'insieme dei numeri primi " , Amer. Matematica. Mensile , vol. 83, n o 6,1976, p. 449-464 ( leggi in linea )( Premio Lester Randolph Ford 1977).
(in) Eric S. Rowland , A Natural Prime-Generating Recurrence , vol. 11, Journal of Integer Sequences,2008, 08.2.8 p. ( Bibcode 2008JIntS..11 ... 28R , arXiv 0710.3217 , leggi online )
(in) William H. Mills, " A prime Representing function " , Bull. Amaro. Matematica. Soc. ,1947, p. 604 e 1196 ( leggi in linea ).
(EN) D. Fridman, J. Garbulsky, B. Glecer, J. Grime e MT Florentin, “ Una costante prime-che rappresenta ” , Amer. Matematica. Mese. , vol. 126, n o 1,gennaio 2019, p. 70-72 ( DOI 10.1080 / 00029890.2019.1530554 , leggi online ).
Suite A249270 di OEIS .
(a) Steven R. Finch, Costanti matematiche , vol. II, Cambridge University Press,2018( leggi in linea ) , p. 171.
Suite A053669 da OEIS: " Numero primo più piccolo che non divide n " .

Vedi anche

Bibliografia

Jean-Paul Delahaye , Wonderful primi numbers: Journey to the heart of aritmetic ,2000[ dettaglio dell'edizione ]
Marcus du Sautoy ( traduzione dall'inglese), The Symphony of Prime Numbers , Parigi, edizioni Héloïse d'Ormesson,2005, 491 p. ( ISBN 2-35087-011-1 )

Link esterno

(it) Eric W. Weisstein , " Prime Formulas " , su MathWorld