Alessandro Zaccagnini ci racconta una delle scoperte più curiose di Conway sui numeri primi.

Tra le scoperte meno note e decisamente sorprendenti di John H. Conway c’è la “macchina per produrre i numeri primi” che vediamo qui sotto illustrata da una simulazione java. Si tratta di una sequenza di 14 frazioni che devono essere combinate secondo certe regole. Le frazioni sono queste:

\[\frac{17}{91} \quad \frac{78}{85} \quad \frac{19}{51} \quad
\frac{23}{38} \quad \frac{29}{33} \quad \frac{77}{29} \quad
\frac{95}{23} \quad \frac{77}{19} \quad \frac{ 1}{17} \quad
\frac{11}{13} \quad \frac{13}{11} \quad \frac{15}{14} \quad
\frac{15}{ 2} \quad \frac{55}{ 1}\]

Partendo dall’input 2, si deve scorrere la lista da sinistra verso destra fino a trovare una frazione (in questo caso la penultima, cioè \(\frac{15}2\)) che moltiplicata per 2 dia un numero intero, in questo caso 15. Con il numero 15 appena ottenuto si riparte dall’estrema sinistra e si ripete lo stesso procedimento, cercando la prima frazione che moltiplicata per 15 dia un numero intero; dobbiamo attendere di arrivare all’ultima frazione \(\frac{55}1\) per trovare di nuovo un numero intero, e cioè 825. Iterando questo procedimento, troviamo la successione \[2 \quad 15 \quad 825 \quad 725 \quad 1925 \quad 2275 \quad 425 \dots\] Conway ha dimostrato che “ogni tanto” questa successione contiene una potenza di 2. La cosa stupefacente è che quando questo accade l’esponente della potenza di 2 è un numero primo! E, viceversa, questa “macchina” produce proprio tutti i numeri primi in sequenza.

La procedura descritta da Conway nasconde un procedimento di divisione per tentativi che corrisponde alla determinazione della successione dei numeri primi, ma in modo estremamente inefficiente. Sono necessarie 19 iterazioni per trovare il numero primo 2, 69 iterazioni per trovare 3, 280 per trovare 5. L’interesse sta nel fatto che una cosa del genere sia possibile, anche se dal punto di vista pratico esistono procedimenti ben piú rapidi per ottenere lo stesso risultato.

In un certo senso, possiamo dire che Conway ha creato un linguaggio di programmazione rudimentale nel quale è possibile esprimere le operazioni aritmetiche di base, necessarie alla determinazione della primalità di un numero intero, e poi ha “travestito” il relativo algoritmo scritto in questo linguaggio in operazioni fra frazioni. È una specie di macchina di Turing per i numeri primi: si tratta di uno strumento di indagine ideale e non pratico. Serve a dimostrare che la complessità dei numeri primi può essere caratterizzata in modo finito, cosa che ha un interesse indipendente come ho raccontato in altri articoli qui su MaddMaths!, per esempio in Code di rospo e denti di drago — Formule per i numeri primi.

Una spiegazioni più dettagliata si può trovare nel mio articolo Macchine per produrre i numeri primi, apparso nel 2016 sulla rivista UMI (e consultabile a questo link) o sulla pagina Fractran di Wikipedia.

Potete ad avviare la simulazione qui sotto (è un file che richiede java, in caso fosse bloccato, autorizzare il browser ad eseguirlo) con Start e fermarla con Stop, e anche ad aumentare o diminuire la velocità con il pulsante Speed.

<ifram

Alessandro Zaccagnini