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

La caccia a numeri primi sempre maggiori è diventata nei secoli una specie di sfida tra matematici, impegnati a strapparsi il record, sia per il massimo primo, sia per il massimo di qualche particolare categoria.

La seguente tabella riporta il record successivi del più grande numero primo noto.

Numero

Cifre

Anno

Scopritore

Metodo

217 – 1

6

1588

Cataldi

Divisioni successive

219 – 1

6

1588

Cataldi

Divisioni successive

231 – 1

10

1750

Eulero

Divisioni selettive

(2^59 – 1) / 17951

13

1867

Landry

Divisioni selettive

2127 – 1

39

1876

Lucas

Lucas

(2^148 + 1) / 17

44

1951

Ferrier

Teorema di Proth

180(2127 – 1)2 + 1

79

1951

Miller e Wheeler

Teorema di Proth

2521 – 1

157

1952

Robinson

Lucas – Lehmer

2607 – 1

183

1952

Robinson

Lucas – Lehmer

21279 – 1

386

1952

Robinson

Lucas – Lehmer

22203 – 1

664

1952

Robinson

Lucas – Lehmer

22281 – 1

687

1952

Robinson

Lucas – Lehmer

23271 – 1

969

1957

Riesel

Lucas – Lehmer

24253 – 1

1332

1961

Hurwitz

Lucas – Lehmer

24423 – 1

1332

1961

Hurwitz

Lucas – Lehmer

29689 – 1

2917

1963

Gillies

Lucas – Lehmer

29941 – 1

2993

1963

Gillies

Lucas – Lehmer

211213 – 1

3376

1963

Gillies

Lucas – Lehmer

219937 – 1

6002

1971

Tuckerman

Lucas – Lehmer

221701 – 1

6533

1978

Noll & Nickel

Lucas – Lehmer

223209 – 1

6987

1979

Noll

Lucas – Lehmer

244497 – 1

13395

1979

Nelson & Slowinski

Lucas – Lehmer

286243 – 1

25962

1982

Slowinski

Lucas – Lehmer

2132049 – 1

39751

1983

Slowinski

Lucas – Lehmer

2216091 – 1

65050

1985

Slowinski

Lucas – Lehmer

391581 • 2216193 – 1

65087

1989

Brown, Noll, Parady, Smith, Smith e Zarantonello

Lucas – Lehmer

2756839 – 1

227832

1992

Slowinski e Gage

Lucas – Lehmer

2859433 – 1

258716

1994

Slowinski e Gage

Lucas – Lehmer

21257787 – 1

378632

1996

Slowinski e Gage

Lucas – Lehmer

21398269 – 1

420921

1996

Armengaud, (GIMPS).

Lucas – Lehmer

22976221 – 1

895932

1997

Spence (GIMPS)

Lucas – Lehmer

23021377 – 1

909526

1998

Clarckson (GIMPS)

Lucas – Lehmer

26972593 – 1

2098960

1999

Hajratwala (GIMPS).

Lucas – Lehmer

213466917 – 1

4053946

2001

Cameron (GIMPS)

Lucas – Lehmer

220996011 – 1

6320430

2003

Shafer (GIMPS)

Lucas – Lehmer

224036583 – 1

7235733

2004

Findley (GIMPS)

Lucas – Lehmer

225964951 – 1

7816230

2004

Novak (GIMPS)

Lucas – Lehmer

230402457 – 1

9152052

2005

Curtis Cooper e Steven Boone (GIMPS)

Lucas – Lehmer

232582657 – 1

9808358

2006

Curtis Cooper e Steven Boone (GIMPS)

Lucas – Lehmer

237156667 – 1

11185272

2008

Hans-Michael Elvenich (GIMPS)

Lucas – Lehmer

243112609 – 1

12978189

2008

Edson Smith (GIMPS)

Lucas – Lehmer

257885161 – 1

17425170

2013

Curtis Cooper (GIMPS)

Lucas – Lehmer

274207281 – 1

22338617

2016

Curtis Cooper (GIMPS)

Lucas – Lehmer

277232917 – 1

23249425

2017

Curtis Cooper (GIMPS)

Lucas – Lehmer

282589933 – 1

24862048

2018

Patrick Laroche (GIMPS)

Lucas – Lehmer

Il record di Lucas fu l’ultimo stabilito lavorando a mano.

 

Il record di Ferrier venne stabilito con una calcolatrice meccanica; è il record per il massimo primo dimostrato tale senza l’aiuto di un elaboratore elettronico ed è estremamente improbabile che qualcuno avrà mai la pazienza di tentare di batterlo. I record successivi sono stati tutti stabiliti con elaboratori elettronici.

 

Il record di Miller e Wheeler fu il primo stabilito utilizzando un elaboratore elettronico; da allora i record sono sempre stati stabiliti grazie a macchine sempre più sofisticate e ritengo lo stesso varrà nel futuro, perché anche se si trovasse un metodo relativamente semplice per stabilire se i numeri di una qualche categoria sono primi, con ogni probabilità l’attuazione del metodo richiederà comunque risorse di calcolo automatico: è impensabile anche solo scrivere manualmente un numero di decine di milioni di cifre.

 

Gli ultimi sedici sono stati scoperti da un progetto che ha coinvolto i calcolatori di centinaia di persone in una ricerca distribuita sulla rete.

 

I massimi numeri non di Mersenne dimostrati primi sono:

  • 302627325 • 2530101 + 1, che ha 159585 cifre, trovato da R. Burrowes, P. Jobling e Y. Gallot nel 1999;

  • 19249 • 213018586 + 1, che ha 3918990 cifre, trovato da K. Agafonov nel 2007.

Il massimo primo noto che non sia di una forma particolare, che permetta verifiche di primalità particolarmente efficienti è 392113# + 1 (D. Heuer, 2001) con 169966 cifre.

 

Il massimo primo noto della forma n3k + 1 è 2 • 313782 + 1, che ha 6576 cifre.

 

Il massimo primo noto della forma n10k + 1 è 134088 • 1015030 + 1, che ha 15036 cifre.

 

Come si vede, solo 4 volte dalla fine del Medioevo (in colore nella tabella precedente) primi che non siano primi di Mersenne sono stati, sia pur per breve tempo, i più grandi numeri primi noti. Fino al XVIII secolo il motivo era principalmente che i numeri di Mersenne e di Fermat sono famosi e affascinano i matematici, molto più di numeri relativamente “anonimi”. In seguito il motivo principale è stata l’efficienza del test di Lucas – Lehmer, che permette di stabilire se un numero di Mersenne è primo in numero di passi proporzionale al logaritmo del numero; per primi generici si devono usare altri metodi, che richiedono un numero di operazioni che aumentano molto più velocemente al crescere del numero. A parità di tempo impiegato e operazioni svolte, quindi si riesce a dimostrare la primalità di numeri di Mersenne molto maggiori.

Da notare che mentre 219 – 1 detenne il record per quasi due secoli e 2127 – 1 per 75 anni, in epoca recente il record viene battuto ogni pochi anni e talvolta persino più volte in un anno.

Contattami

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