Don't take life too seriously: it's just a temporary situation

Primi (numeri)

Teoria dei numeri 

Indice

  1. 1. Pagina principale
  2. 2. Proprietà
  3. 3. Distribuzione dei numeri primi
  4. 4. Differenze tra primi consecutivi
  5. 5. Progressioni aritmetiche di numeri primi
  6. 6. Progressioni aritmetiche contenenti numeri primi
  7. 7. Funzioni che producono numeri primi
  8. 8. Esami di primalità
  9. 9. Tabelle di primi
  10. 10. Grandi primi
  11. 11. Primi di forme particolari

Sono state cercate a lungo funzioni capaci di produrre tutti i primi o solo primi o almeno tanti primi al variare di un parametro.

 

Per prima cosa sono stati esaminati i polinomi, perché molto probabilmente per polinomi di grado maggiore di 1 vale qualcosa di analogo al teorema di Dirichlet: la congettura di Bunyakovsky asserisce che dato un polinomio irriducibile a coefficienti interi p(n), tale che non esista un primo che divida tutti i valori assunti dal polinomio al variare di n, (condizione di Bunyakovsky), esistono infiniti valori di n che lo rendono primo.

Una versione più forte è l’ipotesi di Schinzel, che asserisce che dati k polinomi irriducibili a coefficienti interi p1(n), p2(n), ... pk(n), tali che il loro prodotto soddisfi la condizione di Bunyakovsky, esistono infiniti valori di n che li rendono simultaneamente primi.

Le due congetture sono una generalizzazione di quella avanzata da Dickson nel 1904, che riguarda solo un insieme di polinomi lineari, ossia della forma an + b.

La congettura di Bateman – Horn è una versione ancora più forte dell’ipotesi di Schinzel, che aggiunge una stima del numero di primi generati.

 

Per ora nessuno è stato in grado di dimostrare una di queste congetture, tranne che in pochi casi particolari.

 

Si vede facilmente che nessun polinomio può produrre tutti i primi o solo primi; tuttavia alcuni ne possono produrre moltissimi e vari ricercatori si sono sbizzarriti nella caccia a polinomi che ne generino un gran numero; per esempio:

  • 30n –13 produce numeri primi per 411 tra i primi 1000 valori di n;

  • n2 + n + 41 produce primi per tutti i valori di n da 0 a 39 (Eulero) e nessun polinomio della forma n2 + n + a può produrne di più consecutivi;

  • 2n2 + 29 produce primi per tutti i valori di n da 0 a 28;

  • |36n2 – 810n + 2753| produce primi per tutti i valori di n da 0 a 44 (Ruby);

  • 708n6 + 1 produce primi per 218 valori di n inferiori a 1000 (M. Fiorentini, 2017).

 

E. Karst dimostrò nel 1973 che il polinomio di secondo grado che genera il maggior numero di primi per i primi 1000 valori di n è 2n2 – 199, che ne genera 598.

 

Il massimo numero di primi prodotti per valori consecutivi della variabile dipende dal grado del polinomio; i record attuali sono:

  • |103n2 – 3945n + 34381|, per i valori di n da 0 a 45 (Gilbert Fung);

  • n2 – 2999n + 2248541, per i valori di n da 1460 a 1539 (Beiler);

  • |3n3 – 183n2 + 3318n –18757|, per i valori di n da 0 a 46;

  • |n4 – 97n3 + 3294n2 – 45458n + 213589|, per i valori di n da 0 a 49;

  • (n^5 – 133 * n^4 + 6729 * n^3 – 158379 * n^2 + 1720294 * n – 6823316) / 4, per i valori di n da 0 a 56 (Shyam Sunder Gupta).

 

Se non si richiede di produrre primi per valori consecutivi della variabile, anche tra i polinomi di secondo grado si può far di meglio; per n da 0 a 1000000, infatti:

  • il famoso polinomio di Eulero n2 + n + 41 produce 261081 primi;

  • il polinomio 2n2 – 199 (R.A. Milin e H.C. Williams, 1989) ne produce 280454;

  • il polinomio n2 + n + 72491 (N.G.W.H. Beeger, 1939) ne produce 290492.

 

Chiaramente i cacciatori di record si limitano a polinomi a coefficienti interi o al massimo razionali, che producano un numero di primi molto superiore al grado, perché si può facilmente costruire un polinomio di grado n che per valori da 0 a n della variabile assuma come valore n + 1 primi a piacere, anche consecutivi (v. costante di Magata).

 

Il passo successivo è costituito da funzioni con l’argomento come esponente, che possono produrre infiniti primi, sebbene non tutti. Alcuni sono quindi andati a caccia di record tra le espressioni esponenziali, cercandone di semplici, che producano un certo numero di primi per valori differenti di n:

  • 4n + 37 è primo per n da 1 a 7;

  • 4n + 4503 è primo per n da 1 a 14;

  • 4n + 1158174141556287 è primo per n da 1 a 18 (1158174141556287 è il minimo intero con questa proprietà);

  • 10n + 5893321 è primo per n da 0 a 11;

  • 26373004 • 10n + 1 è primo per n da 1 a 8;

  • 857095380 • 2n + 1 è primo per n da 0 a 8;

  • 64606701602327559675 ± 2n è primo per n da 1 a 8 (Phil Carmody, 2003).

 

Se si aggiunge all’arsenale la funzione Massimo intero non superiore a n si aprono interessanti possibilità: si possono infatti scrivere funzioni che producono infiniti primi o addirittura solo primi.

 

Nel 1953 I.I. Piatetski-Shapiro dimostrò che la sequenza Massimo intero non superiore a n^c contiene infiniti primi per 1 < c < 12 / 11.

 

H.W. Mills dimostrò che esiste una costante θ tale che Massimo intero non superiore a θ^(3^n) è primo per qualsiasi valore di n maggiore di zero (v. costante di Mills).

In seguito sono state trovate numerose altre formule simili, tra le quali una veramente curiosa è quella trovata da E.M. Wright nel 1951: Massimo intero non superiore a 2^(2^(2^ ... ^K)), dove K è circa 1.9287800; aumentando il numero di 2 nella “torre” di esponenti si ottengono infiniti primi, a partire da 3, 13, 16381. Nel 1954 Wright dimostrò che esiste un insieme infinito non numerabile di valori possibili per K, non denso in alcun punto e di misura nulla.

Dal postulato di Bertrand segue l’esistenza di infiniti numeri del genere; il minimo è 1.251647597790463017594432053623 (R.L. Graham, D.E. Knuth e O. Patashnik), che genera i primi 2, 5, 37, 137438953481; non riporto il successivo, perché ha 41373247571 cifre.

Il massimo possibile valore per K è circa 1.9287821872.

Qui trovate le prime 117 cifre decimali del massimo valore possibile per K (Eric W. Weisstein, Charles R Greathouse IV, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

R.L. Graham, D.E. Knuth e O. Patashnik dimostrarono che il minimo valore possibile per K è circa 1.251647597790463017594432053623346969, (Benoit Cloitre, Frank Ellermann, Charles R Greathouse IV, The Online Encyclopedia of Integer Sequences http://oeis.org), che genera i primi 2, 5, 37, 137438953481; non riporto il successivo, perché ha 41373247571 cifre.

 

La somma dei reciproci dei primi generati in questo modo e la somma dei reciproci dei loro quadrati sono numeri di Liouville e sono quindi trascendenti (Robert Baillie, 2019).

 

J.M. Gandhi pubblicò nel 1971 la formula Formula per il calcolo di p(n), capace di produrre l’n-esimo primo; la difficoltà sta nel fatto che per calcolare pn bisogna conoscere tutti i primi inferiori.

 

Si possono anche scrivere funzioni che producono tutti i primi, però bisogna in un certo senso barare, utilizzando costanti, per calcolare le quali bisogna di fatto conoscere i primi che si vogliono produrre.

Per esempio, per ogni numero naturale k, si può calcolare la costante Formula per il calcolo di α(k), dopodichè Formula per il calcolo di p(n). Per k = 2, α(k) ≈ 1.1973727646 e la formula genera tutti i primi in ordine.

 

Un altro esempio è dato dalla ricorrenza Formula per il calcolo di f(n), con Formula per il calcolo di f(1), che genera tutti i primi in ordine perché p(n) uguale al massimo primo non superiore a f(n).

Qui trovate le prime 100 cifre decimali di f1 (Jean-François Alcover, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

La funzione f(n) = 2 + (2(n – 1)! mod n) produce tutti i primi se n varia tra gli interi positivi. Si tratta di una semplice applicazione del teorema di Wilson, infatti f(n) = n se e solo se n è primo, altrimenti f(n) = 2, ma naturalmente la complessità del calcolo di n! la rende inutile per valori anche solo moderatamente grandi di n.

 

Hardy e Ramanujan dimostrarono che esiste una una formula per il calcolo di pn, che non utilizza costanti che si possono ricavare solo conoscendo già i numeri primi: Formula per il calcolo di p(n), dove ωp, k è una certa radice 24-esima dell’unità, la seconda somma va calcolata per tutti gli interi minori di k e primi rispetto a k e Formula per il calcolo di Ψk(n). La formula non ha applicazioni pratiche, in quanto il calcolo di pn tramite essa è più complicato rispetto ad altri metodi.

 

Frank Buss definì una funzione che sembra capace di produrre solo numeri primi; ecco la sua “ricetta”:

  • si inizia con f(1) = 1;

  • si calcola B(n) prendendo il primo successivo a f(n) + 1 e sottraendo f(n);

  • si calcola f(n + 1) = f(n)B(n).

La procedura assomiglia a quella per il calcolo dei primi di Fortune e probabilmente ha successo per lo stesso motivo.

Buss suppose che la procedura generi solo primi e tutti i primi (v. congettura di Buss (I)); la procedura di Fortune invece non genera mai 11 e genera due volte alcuni primi, il minimo dei quali è 23.

 

E. Rowland dimostrò che definendo la sequenza a1 = 7, an = an – 1 + MCD(n, an – 1)), le differenze anan – 1 sono 1 o un numero primo dispari. In questo modo si ottengono i primi 5, 3, 11, 3, 23, 3, 47, 3, ... e una valanga di 1. Non è noto se la sequenza contenga tutti i numeri primi dispari; il minimo che non appaia tra i primi 10000 prodotti in questo modo è 2587.

 

Una procedura molto più rigorosa ed elegante si deve al genio di J.H. Conway: si inizia con 2 e ogni volta si moltiplica l’ultimo numero ottenuto per la prima delle frazioni del seguente elenco che renda il risultato intero: Frazioni proposte da Conway per generare i numeri primi.

I primi passi producono i numeri 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4. Di tanto in tanto si ottengono potenze di 2: ebbene, gli esponenti di queste sono tutti e soli i numeri primi, in ordine ascendente! La procedura produce infatti 8 = 23 dopo altri 50 passi, 32 = 25 dopo altri 211 e così via.

Non si tratta di una mirabolante scoperta, ma di una sorta di macchina di Turing, che utilizza una versione del crivello di Eratostene per trovare i numeri primi, il tutto abilmente mascherato. Mi manca purtroppo lo spazio per spiegare i dettagli del funzionamento del congegno; rimando il lettore interessato all’articolo di Conway citato nella bibliografia.

 

Un’altra possibilità è utilizzare polinomi in più variabili: sono infatti stati trovati alcuni polinomi in due variabili che generano infiniti primi (v. congettura di Bunyakovsky).

 

Esiste una formula capace in un certo senso di produrre tutti i numeri primi: guardate il seguente fantastico polinomio di 25° grado, con 26 variabili (James P. Jones, Hideo Wada, Daihachiro Sato e Douglas Wiens, 1976):

(k + 2)(1 – (wz + h + jq)2 – ((gk + 2g + k + 1)(h + j) + hz)2 – (2n + p + q + ze)2 – (16(k + 1)3(k + 2)(n + 1)2 + 1 – f2)2 – (e3(e + 2)(a + 1)2 + 1 – o2)2 – ((a2 – 1)y2 + 1 – x2)2 – (16r2y4(a2 – 1) + 1 – u2)2 – (((a + u2(u2a))2 – 1)(n + 4dy)2 + 1 – (x + cu)2)2 – (n + l + vy)2 – ((a2 – 1)l2 + 1 – m2)2 – (ai + k + 1 – li)2 – (p + l(an – 1) + b(2an + 2an2 – 2n – 2) – m)2 – (q + y(ap – 1) + s(2ap + 2ap2 – 2p – 2) – x)2 – (z + pl(ap) + t(2app2 – 1) – pm)2).

Sostituendo valori interi non negativi al posto delle 26 variabili, si ottengono interi positivi e negativi: i valori positivi sono tutti e soli i primi!

A prima vista il polinomio sembra complicato e misteriosissimo; un’analisi appena più approfondita però ci aiuta a svelare parte del mistero: il polinomio è il prodotto di (k + 2) e di un polinomio della forma (1 – A2B2C2 – ...), dove A, B, C... sono polinomi. Perche il valore sia positivo, con k > 0, bisogna che questi polinomi siano tutti nulli, nel qual caso il valore è semplicemente k + 2.

Il polinomio può quindi essere sostituito dalle seguenti equazioni:

  • wz + h + jq = 0;

  • (gk + 2g + k + 1)(h + j) + hz = 0;

  • 2n + p + q + ze = 0;

  • 16(k + 1)3(k + 2)(n + 1)2 + 1 – f2 = 0;

  • e3(e + 2)(a + 1)2 + 1 – o2 = 0;

  • (a2 – 1)y2 + 1 – x2 = 0;

  • 16r2y4(a2 – 1) + 1 – u2 = 0;

  • ((a + u2(u2a))2 – 1)(n + 4dy)2 + 1 – (x + cu)2 = 0;

  • n + l + vy = 0;

  • (a2 – 1)l2 + 1 – m2 = 0;

  • ai + k + 1 – li = 0;

  • p + l(an – 1) + b(2an + 2an2 – 2n – 2) – m = 0;

  • q + y(ap – 1) + s(2ap + 2ap2 – 2p – 2) – x = 0;

  • z + pl(ap) + t(2app2 – 1) – pm = 0.

Abbiamo 14 equazioni diofantee in 26 variabili, che risolte ci permettono di calcolare tutti i numeri primi.

Matyasevic dimostrò nel 1971 l’esistenza di un polinomio di grado 21 in 21 variabili con la stessa proprietà, senza pero scriverlo esplicitamente.

 

Una conseguenza interessante è che mentre per dimostrare che un numero è composto bisogna eseguire una moltiplicazione (moltiplicando due fattori per ottenere il numero), si può dimostrare che un numero è primo con 87 operazioni, tra addizioni e moltiplicazioni: tante ne servono, infatti, per calcolare il valore del polinomio, date le variabili. L’interesse, nei due casi, è puramente teorico: nel primo caso, infatti, bisogna conoscere due fattori, nel secondo i valori delle 26 variabili che producono quel particolare primo, in generale estremamente difficili da trovare.

 

Il polinomio è inutile, da un punto di vista pratico, perché non si può stabilire a priori per quali combinazioni di interi si otterrà un numero positivo, quindi primo, ma ha un’enorme importanza teorica: di fatto è una conseguenza di una delle più importanti scoperte matematiche del XX secolo, vale a dire la dimostrazione di Matyasevic dell’impossibilità di risolvere il decimo problema di Hilbert, ossia trovare un algoritmo che risolva in un numero finito di passi una generica equazione diofantea. Combinando tale dimostrazione con altre idee, si è riusciti a dimostrare che per ogni insieme ricorsivamente enumerabile (per il quale cioè sia possibile determinare in un numero finito di passi se un intero vi appartiene) si può scrivere un’equazione diofantea che ha tali interi, e solo quelli, come soluzione. Per di più è sempre possibile limitare il numero di variabili a 14 o il grado a 4, ma riducendo il grado aumenta il numero di variabili e viceversa.

Nel caso dei numeri primi gli stessi autori pubblicarono nel 1976 un polinomio di grado 5 in 42 variabili e Matyasevic dimostrò che è possibile ridurre le variabili a 10, aumentando il grado a circa 1.6 • 1045.

Polinomi del genere sono stati trovati anche per i numeri di Fibonacci, i primi di Mersenne e Fermat e i numeri perfetti (si vedano i rispettivi paragrafi).

Jones dimostrò anche l’esistenza di un polinomio con 58 variabili di grado 4 che è universale, nel senso che cambiando il valore di una variabile si può far sì che si annulli se e solo se un’altra variabile appartiene a un certo insieme, per opportuni valori delle rimanenti. La prima variabile serve in pratica a scegliere l’insieme e permette, in teoria, di scegliere un qualsiasi insieme enumerabile, inclusi i numeri primi, i cubi, i primi di Mersenne ecc.. Naturalmente questo non serve a trovare effettivamente tutti gli appartenenti a un insieme, perché non si sa a priori quali siano le combinazioni di valori delle 57 variabili restanti che consentono al polinomio di annullarsi.

In generale Jones dimostrò che data una teoria assiomatizzabile e una proposizione P, esiste una prova della proposizione all’interno della teoria, che consiste di al massimo 100 tra addizioni e moltiplicazioni. In questo caso però non sappiamo neppure quale sia, in generale, il polinomio che costituisce la prova.

 

Nella direzione opposta è relativamente semplice dimostrare che qualsiasi polinomio in una variabile a coefficienti interi produce infiniti numeri composti. R.C. Buck dimostrò nel 1946 se una funzione razionale (vale a dire un quoziente di polinomi) assume solo valori primi per valori abbastanza grandi della variabile, allora è una costante e nel 1990 D. Sato e E.G. Strauss estesero la dimostrazione alle funzioni algebriche.

Sono noti polinomi che producono un gran numero di numeri composti per valori consecutivi della variabile; in particolare B. Garrison dimostrò nel 1981 che il polinomio n2 + 1 produce sequenze lunghe a piacere di numeri composti (v. congettura di Bunyakovsky).

 

Per ogni polinomio della forma x2 + x + n, esiste un minimo primo p che divide qualche valore assunto per n ≥ 0, ossia tale che tutti i valori generati non sono divisibili per primi inferiori. Luis Rodríguez congetturò che al variare di n tale minimo primo possa essere qualsiasi primo, nessuno escluso. C. Nash dimostrò nel 2000 che la congettura è vera e che per ogni primo p esiste un n < p# tale che p sia il minimo primo che divide qualche valore del polinomio. Infatti, basta prendere n tale che –n mod q non sia congruente a nessun intero della forma k2 + k, per ogni primo q minore di p.

Esistono quindi semplici polinomi di questa forma che non sono mai divisibili per un insieme di primi grande a piacere.

 

Sono state trovate espressioni esponenziali che, pur non avendo una fattorizzazione semplice, non producono primi (v. numeri di Riesel e numeri di Sierpiński (II)).

 

Resta una curiosità il fatto che la sequenza 1, 12, 123, 1234, ... ottenuta concatenando i numeri naturali successivi in notazione decimale non contenga alcun primo, almeno fino al punto in cui è stata esaminata, ovvero per 31506 termini (Weisstein, 2006). Il fatto è piuttosto sorprendente, perché non si vede una buona ragione perché la sequenza non contenga primi, e perché sequenze analoghe in altre basi ne contengono. Per esempio, 123 = 5, 121011123 = 3929, 125 = 7, 123451011121314156 = 4060073996291.

Se la concatenazione avviene in ordine inverso, abbiamo la sequenza 1, 21, 321, che contiene il primo numero primo all’82-esimo termine 8281...321 (Stephan, 1998).

Sono state esaminate anche sequenze analoghe, concatenando varie categorie di numeri:

  • se si concatenano i soli numeri dispari, i primi sono relativamente più abbondanti: 13, 135791113151719 e altri in corrispondenza dei termini 16, 34, 49 e 2570 (Weisstein, 1998), ma nessun altro nei primi 20955 termini (Weisstein, 2006);

  • se si concatenano i quadrati, l’unico primo tra i primi 21120 termini è 149 (Marimutha, 1997);

  • se si concatenano i cubi, non si trovano primi tra i primi 17676 (Weisstein, 2006).

 

Per altre congetture su funzioni che producono numeri primi v. congetture sui numeri primi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.