Tag Archives: numeri primi

Nuovo record per i primi gemelli [Pillole]

I numeri primi gemelli sono le coppie di numeri primi la cui differenza è 2, come 3 e 5 oppure 1019 e 1021. Non si sa se ci sia un numero infinito di tali coppie: nel 2013 Yitang Zhang sorprese la comunità matematica mondiale dimostrando che per lo meno esiste un numero infinito di coppie di primi “cugini”, la cui differenza è minore di un dato limite finito, limite inizialmente fissato a 70 milioni – i matematici non si curano, almeno all’inizio, della grandezza dei numeri usati – e poi abbassato fino a 246 dallo sforzo collettivo di tanti matematici.

Per il momento non resta che cercare coppie di primi gemelli sempre più grandi. Il progetto distribuito PrimeGrid, tra le altre cose, cerca anche queste coppie: è notizia fresca (del 14 settembre) che l’utente Tom Greer ha scoperto quella che al momento è la coppia più grande conosciuta: 2996863034895×2^1290000 ± 1. I due numeri hanno 388342 cifre: tanto per dare un’idea, il record precedente era di poco più di 200000 cifre.

Life e i numeri primi [Pillole]

Sicuramente conoscete Life di Conway. Forse avete anche sentito dire che è stato dimostrato che è equivalente a una macchina di Turing: detto in altro modo, qualunque tipo di computazione che possiamo fare con un qualunque computer può essere simulato da una opportuna configurazione iniziale di Life. Il risultato è teorico, il che significa che nessuno si preoccupa della velocità di esecuzione, ma soprattutto che nessuno si mette ad esplicitare quale configurazione corrisponde al nostro calcolatore di Conway.

Quasi nessuno, per la precisione. Dean Hickerson progettò nel 1991 un generatore di numeri primi. Come potete vedere nel video qui sopra, le 2953 celle della configurazione di partenza emettono alla generazione 120N+100 una “astronave leggera” (il nome di una configurazione in Life) per alcuni specifici valori di N: tutti e soli i numeri primi (diversi da 2 e 3). Esistono anche alcune versioni modificate: la più divertente è a mio parere quella che genera tutti e soli i primi di Fermat 🙂

Come può funzionare una cosa del genere? Come fa l’automa cellulare di Life a creare una successione a prima vista impredicibile come quella dei numeri primi? Il trucco è che applica il crivello di Eratostene, che è un algoritmo perfettamente definito. Se guardate il video, notate delle righe diagonali di astronavi in alto a destra: corrispondono per l’appunto ai numeri primi generati, che cancellano le astronavi relative ai loro multipli. Semplice a vedersi, un po’ meno a crearsi!

(H/T: Math Tango)

L’anti-Goldbach [Pillole]

La congettura di Goldbach afferma che ogni numero pari maggiore di 2 è esprimibile come somma di due numeri primi. A parte il caso eccezionale di 4=2+2, si usano sempre due numeri dispari. Visto che nessuno sa dare una risposta, si può pensare a qualcosa di diverso: per esempio, è vero che ogni numero pari maggiore di 2 è esprimibile come somma di due numeri dispari composti? (con i numeri pari la cosa è ovvia)

Ci sono alcuni numeri per cui questo non è possibile: per esempio 20 e 38. Ma è possibile dimostrare che per i numeri maggiori di 40 il teorema è vero. Come farlo? Semplice. Guardate le uguaglianze seguenti:

10k = 15 + 5(2k-3)
10k+2 = 27 + 5(2k-5)
10k+4 = 9 + 5(2k-1)
10k+6 = 21 + 5(2k-3)
10k+8 = 33 + 5(2k-5)

Ora, per k≥4 tutti i fattori (2kn) valgono almeno 3, e pertanto tutti i secondi membri sono somma di due numeri composti. Visto come cambia tutto nel passare dai numeri primi a quelli composti?