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

Prima dell’introduzione dei calcolatori elettronici scomporre un numero in fattori primi e determinare se un numero sia primo o meno era un lavoro arduo; non sorprende quindi che vari matematici abbiano compilato tabelle di scomposizioni e di numeri primi. Quello che è invece sorprendente è l’estensione di tali tabelle, se pensiamo che erano calcolate a mano.

 

Probabilmente piccole tabelle del genere circolavano sin dall’antichità, la prima della quale si abbiano notizie certe risale al Liber Abaci di Fibonacci e arrivava solo a 109; con tale tabella è possibile determinare se un numero sino a poco oltre 10000 sia primo e apparentemente tanto bastò ai matematici sino al XVI secolo.

 

Con lo sviluppo della teoria dei numeri crebbero le necessità e parallelamente le tabelle. Molti si cimentarono nell’impresa, spesso ripetendo i lavori altrui, dei quali erano all’oscuro, e non senza errori; cito solo alcuni dei record più famosi.

  • Pietro Antonio Cataldi (Bologna, 15/4/1548 – Bologna, 11/2/1626) pubblicò una tabella dei divisori e dei primi sino a 800 (Trattato de’ numeri perfetti, Bologna 1603);

  • Franciscus van Shooten (Leiden, Olanda, 1615 – Leiden, 29/5/1660) pubblicò una tabella dei numeri primi fino a 9979 (Exercitationum mathematicarum libri, Leiden, 1656);

  • Johann Rahn (Töss, Svizzera, 10/3/1622 – Zurigo, Svizzera, 25/5/1676) pubblicò una tabella col più piccolo divisore diverso da 2, 3 e 5 dei numeri sino a 24000 (Algebra, Zurigo 1659);

  • Thomas Brancker (Barnstaple, Inghilterra, 8/1633 – Macclesfield, Inghilterra, 11/1676) tradusse in inglese l’opera di Rahn, estendendo la tabella sino a 100000 (Introduction to Algebra, Londra 1688);

  • John Wallis (Ashford, UK, 21/11/1616 – Oxford, UK, 28/10/1703) corresse gli errori di Brancker (Treatise of Algebra, Londra, 1685);

  • Johann Gottlob Krüger (Halle, Germania, 15/6/1715 – Brunswick, Germania, 6/10/1759) pubblicò nel 1746 nella sua città natale una tabella dei primi fino a 100999, attribuendone il merito del calcolo a Peter Jäger, col titolo, apparentemente errato Gedancken vor der Algebra nebst den Primzahlen von 1 bis 1000000, (Riflessioni sull’algebra e sui numeri primi da 1 a 1000000);

  • A.F. Marci pubblicò nel 1772 una tabella del primi fino a 400000 (Primes “in quater centeni millibus”);

  • J.C. Burckhardt pubblicò una tabella del minimo fattore dei numeri fino a 3 milioni, un milione alla volta, ma per il primo milione si avvalse di lavori altrui (Tables des diviseurs 1 à 3036000, Parigi, 1817, 1814, 1816);

 

La palma della perseveranza va ad Anton Felkel (Kamenz, Polonia, 1740 – Lisbona, 1800?), che compilò nel 1776 una tabella dei fattori diversi da 2, 3 e 5 dei numeri sino a 2 milioni e vent’anni dopo, non riuscendo a rientrare in possesso del manoscritto contenente i numeri superiori a 400000, fu costretto a ricalcolarla, stavolta arrivando a 2856000. Felkel progettava di pubblicare le tavole dei fattori primi fino a 10 milioni, ma pubblicò solo i primi tre volumi, che coprono gli interi fino a 408000; il resto del suo lavoro è andato perduto, anche perché, in assenza di acquirenti, la maggior parte delle copie fu usata per fabbricare cartucce durante la guerra contro i Turchi.

Felkel fu il primo ad avvalersi di un ausilio meccanico per i suoi calcoli: una “macchina” composta da bastoncini scorrevoli, recanti multipli di numeri, che semplificavano il calcolo dei prodotti. Nonostante questo, le sue tavole contengono errori, com’è inevitabile in un lavoro manuale di quell’entità: oltre una quarantina, secondo Denis Roegel, che nel 2012 pubblicò un’analisi dettagliata del lavoro di Feikel.

 

Tali tabelle erano considerate tanto utili ai matematici, che Jean-Baptiste le Rond d'Alembert (Parigi, 16/11/1717 – Parigi, 29/10/ 1783) nel 1780 ne incluse nell’Encyclopédie una dei fattori dei numeri sino a 100000.

 

La maggiore di queste opere si deve a Jakob Philipp Kulik (Lemberg, allora impero Austriaco, oggi Ucraina, 20/4/1793 – Praga, 28/2/1863), che dedicò gli anni dal 1825 alla sua morte alla compilazione della tabella dei divisori degli interi non multipli di 2, 3 e 5 e dei primi sino a 100330201: un manoscritto di 4212 pagine, in 8 volumi (Magnus Canon Divisorum pro omnibus numeris per 2, 3 et 5 non divisibilibus, et numerorum primorum interfacentium ad millies centena millia accuratius ad 100330201 usque) (Grande canone dei divisori per tutti i numeri non divisibili per 2, 3 e 5, e dei primi intercalati, fino a cento milioni, più precisamente fino a 100330201). Sfortunatamente l’opera non venne mai stampata, la tabella è incompleta e il manoscritto del secondo volume, contenente i numeri da 12642600 a 22852800 è andato perso. Oggi una tabella del genere può essere calcolata in pochi minuti da un comune calcolatore personale.

 

La seguente tabella riporta solo i record, mentre per maggiori informazioni rimando all’accuratissimo History of the Theory of Numbers e al centinaio di note bibliografiche sull’argomento ivi contenute.

Anno

Autore

Limite

Contenuto

1202

Leonardo Fibonacci

109

Scomposizione in fattori

1603

Pietro Antonio Cataldi

800

Scomposizione in fattori

1656

Franciscus van Shooten

9979

Numeri primi

1659

Johann Rahn

24000

Il minimo fattore diverso da 2, 3 e 5

1688

Thomas Brancker

100000

Il minimo fattore diverso da 2, 3 e 5

1746

Johann Gottlob Krüger

100999

Numeri primi

1772

A.F. Marci

400000

Numeri primi

1776

Anton Felkel

2000000

Fattori diversi da 2, 3 e 5

1796

Anton Felkel

2856000

Fattori diversi da 2, 3 e 5

1817

J.C. Burckhardt

3000000

Il minimo fattore

1863

J.P. Kulik

100330201

Fattori degli interi non multipli di 2, 3 o 5

1887

Simony

16384

Numeri primi in base 2

1894

E. Suchanek

100000

Numeri primi in base 2

1909

D.N. Lehmer

10017000

Fattori dei numeri non multipli di 2, 3, 5 o 7

1914

D.N. Lehmer

10006721

Numeri primi

1959

C.L. Baker e F.J. Gruenberger

104395289

Numeri primi

 

Il calcolatore elettronico personale ha reso tabelle del genere inutili, perché oggi si può scomporre in fattori primi un numero di una ventina di cifre in meno di un secondo; l’ultima tabella del genere fu pubblicata nel 1959 da C.L. Baker e F.J. Gruenberger: conteneva i numeri primi sino a 104395289 ed era distribuita su 12 microfotografie, ciascuna (tranne prima e ultima) riproducente 39 pagine di 1250 primi.

 

Parallelamente furono pubblicate ed estese tabelle di primi di forme particolari, come i primi di Mersenne, raggiungendo limiti talvolta incredibili, considerando che i calcoli erano svolti manualmente.

 

La ricerca di numeri primi in un certo intervallo è un’operazione noiosa e in gran parte puramente meccanica, quindi non stupisce che da parecchio tempo si sia cercato di automatizzarla.

D.H. Lehmer, figlio di D.N. Lehmer costruì nel 1926 un “crivello” meccanico per la ricerca dei numeri primi, con ingranaggi collegati tramite 19 catene di bicicletta, capace di esaminare 3600 numeri al minuto. Sei anni dopo perfezionò il dispositivo, costruendone uno con 32 catene, in grado di esaminare 300000 numeri al minuto.

Negli anni ’30 Lehmer scompose con macchine del genere vari interi; per esempio, trovò il fattore 174763 di 295 – 1 con un crivello fotoelettrico.

Successivamente meccanismi elettromeccanici soppiantarono quelli puramente meccanici (lo stesso Lehmer ne costruì nel 1966 uno capace di esaminare un milione di numeri al secondo) e in tempi più recenti il compito fu affidato a calcolatori elettronici.

Contattami

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