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
  12. 12. Somme che coinvolgono numeri primi
  13. 13. Prodotti che coinvolgono numeri primi
  14. 14. Rappresentazioni di interi come somma di numeri primi
  15. 15. Proprietà basate sulle cifre
  16. 16. Categorie di primi

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 un intervallo limitato di valori della variabile; la tabella seguente mostra alcuni esempi.

Polinomio

Primi generati per n da 0 a 100

Primi generati per n da 0 a 1000

Primi generati per n da 0 a 106

Scopritore e anno

|41n2 – 4641n + 88007|

90

590

292968

Vittorio Ornago, 2020

|41n2 + 33n – 43321|

79

572

292929

N. Boston e M.L. Greenwood, 1995

|41n2 – 3477n + 30389|

90

575

292581

Vittorio Ornago, 2020

n2 + n + 72491

69

611

290492

N.G.W.H. Beeger, 1939

|2n2 – 199|

88

597

280464

R.A. Milin e Hugh C. Williams, 1989

n2 – 161n + 6521

94

612

261140

 

n2 – 129n + 4201

96

609

261129

Vittorio Ornago, 2020

n2 – 79n + 1601

96

603

261115

E.B. Escott, 1899

n2 + n + 41

87

582

261081

Legendre, 1798

n2 + n + 3399714628553118047

24

235

251841

Michael John Jacobson, Jr., 1995

|30n – 13|

57

412

232318

 

708n6 + 1

40

218

96630

M. Fiorentini, 2017

 

E. Karst dimostrò nel 1973 che |2n2 – 199| è il polinomio della forma an2 + b che genera il maggior numero di primi per n da 0 a 1000.

Il polinomio n2 + n + 3399714628553118047 genera 2517022 primi per n da 0 a 107.
 

Un caso particolare è quello dei polinomi che producono numeri primi per valori consecutivi della variabile, a partire da 0. Alcuni dei migliori risultati noti sono riassunti nella tabella seguente; per ciascuno è riportato il numero di primi generati (tra parentesi il numeri di primi differenti, se inferiore).

Polinomio

Primi generati

Scopritore

|(n^5 – 133 * n^4 + 6729 * n^3 – 158379 * n^2 + 1720294 * n – 6823316) / 4|

57

Dress e Landreau, 2002

|(n^6 – 126 * n^5 + 6217 * n^4 – 153066 * n^3 + 1987786 * n^2 – 13055316 * n + 34747236) / 36|

55

Wroblewski e Meyrignac, 2006

|n4 – 97n3 + 3294n2 – 45458n + 213589|

50 (49)

Beyleveld, 2006

|n5 – 99n4 + 3588n3 – 56822n2 + 348272n – 286397|

47

Wroblewski e Meyrignac, 2006

|–66n3 + 3845n2 – 60897n + 251831|

46

Kazmenko e Trofimov, 2006

|36n2 – 810n + 2753|

45

Gilbert Fung e Ruby

|3n3 – 183n2 + 3318n – 18757|

47 (43)

S.M. Ruiz, 2005

|47n2 – 1701n + 10181|

43

Gilbert Fung e Ruby

|103n2 – 3945n + 34381|

43

Gilbert Fung

n2n + 41

41 (40)

Eulero, 1772

|42n3 + 270n2 – 26436n + 250703|

40

Wroblewski e Meyrignac, 2006

4n2 – 154n + 1523

40

Marius Coman

9n2 – 231n + 1523

40

Marius Coman

|137n2 – 4043n + 27277|

40

Vittorio Ornago, 2020

|139n2 – 3453n + 11701|

39

Vittorio Ornago, 2020

193n2 – 6251n + 51899

37

Vittorio Ornago, 2020

|67n2 – 975n – 3251|

37

Vittorio Ornago, 2020

12n2 – 4374n + 74071

36

Vittorio Ornago, 2020

|4n2 + 12n – 1583|

35

Marius Coman

43n2 – 537n + 2971

35

J. Brox, 2006

|16n2 – 446n + 2777|

34

Vittorio Ornago, 2020

|41n2 – 1251n + 5801|

33

Vittorio Ornago, 2020

25n2 – 1185n + 14083

32

Marius Coman

|8n2 – 488n + 7243|

62 (31)

F. Gobbo, 2005

|8n2 – 8n – 197|

31

Marius Coman

|32n2 – 944n + 6763|

31

Marius Coman

16n2 – 300n + 1447

30

Marius Coman

6n2 – 342n + 4903

58 (29)

J. Brox, 2006

2n2 – 112n + 1597

57 (29)

Vittorio Ornago, 2020

2n2 + 29

29

Legendre, 1798

6n2 + 6n + 31

29

B. Van der Pol e B. Speziali, 1951

16n2 – 200n + 683

28

Vittorio Ornago, 2020

|2n2 – 108n + 1277|

55 (27)

Davide Rotondo, 2020

|4n2 – 212n + 2411|

54 (27)

Davide Rotondo, 2020

8n2 + 88n + 43

26

Marius Coman

|7n2 – 371n + 4871|

24

F. Gobbo, 2005

|9n2 – 405n + 2753|

47 (24)

Davide Rotondo, 2020

3n2 + 3n + 23

22

A. Lévy, 1914

n4 + 29n2 + 101

20

E. Pegg Jr., 2005

10n2 + 19

19

Vittorio Ornago, 2020

3n2 + 39n + 37

18

A. Bruno, 2009

n2 + n + 17

16

Legendre

4n2 + 4n + 59

14

Honaker

2n2 + 11

11

 

n3 + n2 + 17

11

 

 

Il polinomio n2 + n + 41 è noto come “polinomio di Eulero”, ma in realtà fu proposto da Legendre nel 1798; Eulero nel 1772 propose il polinomio n2n + 41, che produce primi per n da 0 a 39.

R.A. Mollin dimostrò nel 1997 che esistono famiglie infinite di polinomi quadratici che generano almeno 41 primi per valori consecutivi della variabile, ottenibili da quello di Legendre sostituendo n con 3n – 39 – 3k o con 2n – 39 – 2k e che sostituendo n con n – 40 – k si ottengono polinomi che generano 80 primi consecutivi (40 differenti, ciascuno ripetuto due volte); il primo caso di questi, n2 – 79n + 1601 fu scoperto da E.B. Escott nel 1899; un altro caso è il polinomio n2 – 161n + 6521 riportato sopra.

Da un polinomio che genera m primi per i valori della variabile n da 1 a m – 1 se ne ricava un altro, che genera gli stessi primi, sostituendo n con m – 1 – n. Per esempio, dal polinomio |103n2 – 3945n + 34381| sostituendo n con 42 – n si ottiene il polinomio |103n2 – 4707n + 50383| (Speiser, 2005). Solo se i primi generati sono simmetrici rispetto a un valore centrale il nuovo polinomio è identico al precedente. Per esempio, sostituendo n con 61 – n nel polinomio |8n2 – 488n + 7243| si ottiene nuovamente lo stesso polinomio.

 

Gli unici valori di k tali che il polinomio n2 + n + k generi primi per n da 0 a k – 2 sono: 2, 3, 5, 11, 17 e 41. R.A. Mollin dimostrò nel 1997 che se è vera la congettura di Dickson, esistono polinomi della forma n2 + n + k che generano primi per tutti i valori di n da 0 a m, per qualsiasi m, tuttavia non è stato trovato alcun polinomio di questa forma con k < 1018 che generi più di 40 primi (R.F. Lukes, C.D. Patterson e Hugh C. Williams, 1995).

 

Gli unici valori di k tali che il polinomio 2n2 + k generi primi per n da 0 a k – 2 sono: 3, 5, 11 e 29.

 

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).

 

Una curiosità è rappresentata dai seguenti polinomi, che generano primi “isolati”; ovvero non gemelli, quindi con differenza almeno uguale a 4 rispetto al primo più vicino.

Polinomio

Primi generati

Scopritore

|5n2 – 1295n + 18787|

27

Vittorio Ornago, 2020

|21n2 – 1995n + 2473|

25

Vittorio Ornago, 2020

441n2 – 9303n + 49103

23

Vittorio Ornago, 2020

|15n2 – 885n + 2393|

20

Vittorio Ornago, 2020

|481n2 – 17797n + 129959|

38 (19)

Vittorio Ornago, 2020

|15n2 – 525n + 4523|

36 (18)

Vittorio Ornago, 2020

 

Si dimostra facilmente che per qualsiasi valore di k esistono infiniti polinomi di primo grado che generano infiniti primi con differenza almeno 2k dal primo più vicino, per valori non consecutivi della variabile. Per esempio:

  • i primi generati dal polinomio 15n + 22 hanno differenza almeno 4 dal primo più vicino;

  • i primi generati dal polinomio 105n + 52 hanno differenza almeno 6 dal primo più vicino;

  • i primi generati dal polinomio 1155n + 1139 hanno differenza almeno 8 dal primo più vicino;

  • i primi generati dal polinomio 1155n + 211 hanno differenza almeno 10 dal primo più vicino.

 

Il passo successivo è costituito da funzioni con l’argomento come esponente, che potrebbeo produrre infiniti primi. Alcuni sono quindi andati a caccia di record tra le espressioni esponenziali, cercandone di semplici, che producano un certo numero di primi per valori consecutivi di n. La tabella seguente riassume alcuni dei migliori risultati.

Funzione

Valori di n che generano primi

Scopritore

64606701602327559675 ± 2n

[1 .. 8]

Phil Carmody, 2003

857095380 • 2n + 1

[0 .. 8]

 

|2n – 45|

[1 .. 9]

Vittorio Ornago, 2020

|3n – 1330|

[1 .. 10]

Vittorio Ornago, 2020

4n + 1158174141556287

[1 .. 18]

Jens Kruse Andersen, 2007

4n + 4503

[1 .. 14]

 

|4n – 2918139993|

[1 .. 13]

Vittorio Ornago, 2020

|4n – 3335|

[1 .. 12]

Vittorio Ornago, 2020

4n + 37

[1 .. 7]

 

5n + 8357786976

[1 .. 13]

Vittorio Ornago, 2020

5n + 2496396

[1 .. 12]

Vittorio Ornago, 2020

5n + 9618

[0 .. 11]

Vittorio Ornago, 2020

6n + 11329021

[1 .. 10]

Vittorio Ornago, 2020

|7n – 16397810|

[1 .. 11]

Vittorio Ornago, 2020

|8n – 1798335|

[1 .. 10]

Vittorio Ornago, 2020

9n + 3649081192

[1 .. 14]

Vittorio Ornago, 2020

|9n – 3213482|

[1 .. 13]

Vittorio Ornago, 2020

9n + 73017652

[1 .. 12]

Vittorio Ornago, 2020

|10n – 69970971| [1 .. 11] Vittorio Ornago, 2020

10n + 5893321

[1 .. 10]

 

26373004 • 10n + 1

[1 .. 8]

 

11n + 595207782

[1 .. 12]

Vittorio Ornago, 2020

11n + 139692

[1 .. 10]

Vittorio Ornago, 2020

|12n – 52115|

[1 .. 9]

Vittorio Ornago, 2020

14n + 10865937

[1 .. 10]

Vittorio Ornago, 2020

16n + 11440309507

[1 .. 14]

Vittorio Ornago, 2020

20n + 10219209

[1 .. 10]

Vittorio Ornago, 2020

21n + 394120018

[1 .. 12]

Vittorio Ornago, 2020

21n + 6772768

[1 .. 11]

Vittorio Ornago, 2020

22n + 11486335

[1 .. 10]

Vittorio Ornago, 2020

|23n – 128070|

[1 .. 11]

Vittorio Ornago, 2020

|25n – 1020074|

[1 .. 10]

Vittorio Ornago, 2020

|30n – 25116839|

[1 .. 11]

Vittorio Ornago, 2020

|34n – 1139075|

[1 .. 10]

Vittorio Ornago, 2020

36n + 494515091

[1 .. 12]

Vittorio Ornago, 2020

36n + 19950305

[1 .. 11]

Vittorio Ornago, 2020

39n + 59068

[0 .. 8]

Vittorio Ornago, 2020

42n + 2030075

[1 .. 10]

Vittorio Ornago, 2020

|51n – 1361492|

[0 .. 10]

Vittorio Ornago, 2020

53n + 269460

[0 .. 9]

Vittorio Ornago, 2020

|55n – 3857718|

[0 .. 10]

Vittorio Ornago, 2020

56n + 5915163

[1 .. 10]

Vittorio Ornago, 2020

64n + 16498713

[1 .. 10]

Vittorio Ornago, 2020

|69n – 3857718|

[0 .. 9]

Vittorio Ornago, 2020

|76n – 6404373|

[1 .. 10]

Vittorio Ornago, 2020

77n + 4996290

[0 .. 11]

Vittorio Ornago, 2020

|91n – 271554|

[0 .. 9]

Vittorio Ornago, 2020

99n + 1084828

[0 .. 9]

Vittorio Ornago, 2020

3n + 2n + 350424

[1 .. 13]

Vittorio Ornago, 2020

4n – 2n + 9281

[0 .. 12]

Vittorio Ornago, 2020

7n – 2n + 42003134

[1 .. 13]

Vittorio Ornago, 2020

8n – 2n + 489611147

[1 .. 12]

Vittorio Ornago, 2020

15n – 2n + 73959870

[1 .. 12]

Vittorio Ornago, 2020

 

Il minimo intero k che permetta di generare primi per n da 1 a 18 con un polinomio della forma 4n + k è 1158174141556287.

 

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 f(1) uguale alla somma dei reciproci dei primoriali (v. primoriali), che genera tutti i primi in ordine perché p(n) uguale al massimo primo non superiore a f(n).

 

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 344869 termini. 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 (R.W. Stephan, 1998) e il successivo al 37765-esimo termine (Eric W. Weisstein, 2015).

Sono state esaminate anche sequenze analoghe, concatenando varie categorie di numeri, come i soli numeri dispari, i numeri triangolari, i quadrati, i cubi, sia in ordine diretto che inverso; v. numeri di Smarandache e congetture sui numeri di Smarandache.

 

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

Da un polinomio che genera m primi per i valori della variabile n da 1 a m – 1 se ne ricava un altro, che genera gli stessi primi, sostituendo n con m – 1 – n. Per esempio, dal polinomio |103n2 – 3945n + 34381| sostituendo n con 42 – n si ottiene il polinomio |103n2 – 4707n + 50383| (Speiser, 2005). Solo se i primi generati sono simmetrici rispetto a un valore centrale il nuovo polinomio è identico al precedente. Per esempio, sostituendo n con 61 – n nel polinomio |8n2 – 488n + 7243| si ottiene nuovamente lo stesso polinomio.

Contattami

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