I numeri di Stern

Cosa sono i numeri di Stern? Per raccontarlo, prendo un numero dispari, ad esempio 11, e con qualche calcolo manuale vedo che posso scrivere che 11 = 3 + 8 = 3 + 2*2², cioè che 11 è uguale alla somma di un primo (3) e del doppio di un quadrato maggiore di 0.
La stessa cosa non è possibile per il numero dispari 17. Proviamo infatti a calcolare la differenza tra 17 e ciascuno dei primi dispari minori di 17:

3: 17 – 3 = 2*7;
5: 17 – 5 = 2*6;
7: 17 – 7 = 2*5;
11: 17 – 11 = 2*3;
13: 17 – 13 = 2*2.

Nessuna delle differenze è uguale al doppio del quadrato.
Bene, un numero come 17, dispari e non esprimibile come somma di un primo e del doppio di un quadrato maggiore di 0, è chiamato Numero di Stern. Dal momento che 17 è anche primo, allora sarà un Numero primo di Stern.

Ho scoperto i numeri di Stern grazie al problema #46 dell’Euler Project, che chiede qual è il più piccolo numero composto che non può essere espresso come somma di un primo e del doppio di un quadrato maggiore di 0.

La storia dei numeri di Stern

Nel 1752, in una lettera al matematico svizzero Leonhard Euler, il matematico tedesco Christian Goldbach formulò la congettura che qualunque numero dispari potesse essere espresso come somma di un primo e del doppio di un quadrato.
Esattamente 10 anni prima, nel 1742, Goldbach aveva formulato un’altra congettura, quella per cui è passato alla storia della matematica e che ipotizzava che qualunque numero pari potesse essere espresso come somma di due primi.

Una congettura può essere affrontata in due modi: dimostrandone in modo rigoroso l’esattezza (o la fallacia) oppure trovando un contro-esempio che la smentisca. Finché, infatti, si trovano esempi che confermano la congettura, non si può dire nulla di conclusivo.

Per la congettura forte, quella del 1742, ad oggi non è stato trovato alcun contro-esempio e si ritiene che possa essere vera, benché non sia ancora stata trovata una dimostrazione rigorosa.

Bastarono invece poco più di 100 anni per confutare la congettura debole. Il matematico tedesco Moritz Abraham Stern riportò, in una sua pubblicazione del 1854, una coppia di numeri (5777 e 5993) che non seguivano la congettura di Goldbach, che quindi veniva smentita.
Per la sua scoperta, Stern si avvalse di logica matematica, carta e penna, tanta pazienza e l’aiuto dei suoi allievi.

Primi di Stern

Nel suo viaggio alla verifica della congettura, Stern si accorse anche che per alcuni primi, come il 17 visto prima, l’unico modo per verificare la congettura era di considerarlo come somma di sé stesso e del doppio di un quadrato nullo:

17 = 17 + 2 * 0².

In altre parole, per questi primi non esiste un quadrato maggiore 0 che lo scomponga nella somma voluta. Stern trovò che questi numeri primi erano: 3, 17, 137, 227, 977, 1187, 1493.
Pur avendo verificato fino a 9.000, non era emerso alcun altro primo con quella caratteristica.

Ne esistono altri?

Stern e i suoi allievi avevano esplorato i dispari fino a 9.000. Cosa accade dopo?
Una volta risolta la congettura debole di Goldbach (confutandola), infatti, si affaccia immediatamente un’altra domanda: i numeri che violano quella congettura sono in numero finito o infinito?

Per adesso, pur avendo esplorato il campo dei dispari fino a 2*10¹³, non è stato trovato alcun nuovo numero di Stern.

Un programma per trovare i numeri di Stern

Mi sono cimentato nel problema 46 dell’Euler Project, con l’algoritmo più diretto che si possa immaginare:

esploro i numeri dispari e non primi n, a partire da 3;
verifico se n è uguale alla somma di un primo e di un quadrato;
se lo è, stampo n e mi fermo;
altrimenti continuo.

Il programma si ferma dopo aver stampato 5777. Bingo!

Per velocizzare l’esecuzione del programma, è preferibile costruirsi una lista di numeri primi e una lista di doppi di quadrati. In questo modo è sufficiente provare la somma di tutti gli elementi della prima lista con tutti gli elementi della seconda lista, fermandosi quando la somma è uguale a n oppure eccede n.

Il programma che ho messo giù fa esattamente questo, senza eccessi di fantasia.

Un algoritmo più furbo

Solo dopo aver inserito la soluzione corretta, il sito dell’Euler Project consente di dare un’occhiata a una selezione di soluzioni proposte in precedenza da altri. In questo caso ho trovato una realizzazione dello stesso algoritmo che ho utilizzato io (d’altra parte non mi sembra ci siano alternative), ma molto più efficiente.
Le liste dei primi e del doppio dei quadrati vengono infatti create non a priori, come ho fatto io, ma costruite via via, maneggiando quindi liste mai più lunghe del necessario.

Con poche semplici modifiche, quel programma può essere adattato per guardare oltre il 5777, andando a cercare i numeri di Stern, primi e non primi, fino a un limite programmabile.

Il codice

from sympy import isprime
import time
t0 = time.time()
imax = 1000000
primi = []
doppioq = [2]
i = 1
j = 1
while i < imax:
    i += 2
    if isprime(i):
        primi.append(i)
    if doppioq[-1] < i:
        j += 1
        doppioq.append(2*j**2)
    a, b = len(primi)-1, 0
    while True:
        while primi[a]+doppioq[b]<i:
            b += 1
        if primi[a] + doppioq[b] == i:
            break
        a, b = a-1, 0
        if a<0:
            comp = '(composto)'
            if i in primi:
                comp = '(primo)'
            print (i,comp)
            break
print ('{:.2f} secondi di elaborazione'.format(time.time()-t0))
print ('ho considerato {} primi e {} quadrati'.format(len(primi), len(doppioq)))

La logica del codice è abbastanza semplice:

le liste primi e doppioq contengono rispettivamente i primi dal 3 in avanti e il doppio dei quadrati via via necessari al test di scomposizione;
per verificare se un numero è dispari, si utilizza la funzione Python isprime;
nella stampa del numero di Stern trovato si evidenzia se è primo o composto;
si utilizza la funzione time per misurare il tempo di esecuzione;
completata la ricerca fino a imax (1.000.000), si stampa, a scopo statistico, anche il numero di primi e doppi di quadrati accumulati.

L’output

Ed ecco l’output del programma, eseguito nell’ambiente del Google Collaboratory (se ne è parlato più volte in questi articoli, ad esempio qui, dove c’è anche il link a un esempio):

3 (primo)
17 (primo)
137 (primo)
227 (primo)
977 (primo)
1187 (primo)
1493 (primo)
5777 (composto)
5993 (composto)
59.96 secondi di elaborazione
ho considerato 78497 primi e 708 quadrati

Poco meno di un minuto. Chissà il prof. Stern cosa avrebbe tirato fuori, se solo avesse avuto accesso a uno dei nostri pc.

Foto di apertura di Gerd Altmann, da Pixabay.