Un numero autobiografico (in inglese “self-descriptive number”) è un numero che scritto in una base b è composto di b cifre, che lette da sinistra a destra indicano quante cifre di quel tipo ci sono nel numero stesso, a partire da 0 fino a b−1. Un esempio potrà chiarire un po’ meglio di che si parla. In base 10 consideriamo il numero 6210001000. La sua prima cifra è un 6, e quindi dice che contiene 6 zeri; la seconda cifra è 2, e quindi contiene due 1; terza e settima cifra sono 1, quindi c’è un 2 e un 6; tutte le altre cifre sono 0, quindi non ci sono quelle cifre nel numero.

Di per sé i numeri autobiografici non sono poi così interessanti. In base 2, 3 e 6 non esistono numeri interessanti. Dalla base 7 in su ce n’è uno solo; in base b la sua prima cifra da sinistra è b−4, la seconda è 2, la terza e quella in posizione b−3 sono 1 e le altre sono 0. Gli altri casi sono 1210₄, 2020₄ e 21200₅. Però Lee Sallows, il massimo esperto mondiale in oggetti autodescritti, ha presentato questo esempio:

Prendete una striscia qualunque, per esempio la C, e una posizione qualunque, per esempio quella corrispondente al 3. La striscia contiene in quella posizione un 4; allora nelle altre due strisce (A e B) ci sono in tutto quattro 3.

La soluzione proposta è unica, almeno in base 10 e con tre strisce? Non ne ho idea…

Ultimo aggiornamento: 2024-11-20 19:06

Non credo nessuno abbia mai imparato a memoria la tabellina del 13. Non che uno ne veda la necessità, a dire il vero: già quella del 12 secondo me è un’esagerazione. Ad ogni modo, questa tabellina ha una proprietà piuttosto strana. I suoi primi termini sono 13, 26, 39, 52: saltiamo insomma il 4 come cifra iniziale. Certo, prima o poi un multiplo di 13 dovrà ben cominciare con 4: tra 399 e 500 ce ne saranno parecchi. Ma dobbiamo appunto arrivare fino a 400, e quindi arrivare oltre 13×30 = 390. (In effetti 13×31 = 403)

Qualche anno fa Christian Lawson-Perfect provò a generalizzare questo risultato: in fin dei conti il 4 non ha nulla di particolare come numero. Lawson-Perfect si chiese dunque quale fosse, dato un numero n, il più piccolo k per cui l’insieme delle prime cifre dei numeri n×1, n×2, …, n×k comprendesse tutte le cifre da 1 a 9. La tabella risultante è mostrata qui sotto:

n     1  2  3  4  5  6  7  8  9 10 11 12 13
k(n)  9 45 27 23 18 15 13 12  9  9  9 42 62

Evidentemente il valore di k(n) non può mai essere inferiore a 9, sennò non possiamo avere tutte le cifre iniziali: è un po’ meno evidente che k(n) non sia mai superiore a 81. Credo che se avessi un po’ di tempo a disposizione potrei dimostrarlo, anche senza verificare quanto scritto nell’articolo di The Aperiodical da cui ho tratto queste informazioni. Vediamo che anche il 2 è piuttosto sfortunato, ma potevamo aspettarcelo perché arrivare a 90 a due a due è lungo; il 13 comunque lo supera di parecchio, per arrivare a un multiplo che cominci per 8. La figura qui sotto, una gif animata presa dall’articolo citato e che mappa il valore di k(n) per n che va da 1 a una potenza di 10, mostra che la struttura è abbastanza autosimilare.

Per i curiosi, il primo numero per cui occorrono i suoi primi 81 multipli per avere tutte e 9 le possibili cifre iniziali è 112, e in genere ceil(10ⁱ/9) richiede 81 multipli per tutti gli i maggiori o uguali a 3. Questo è facile da dimostrare: volete cimentarvi?

La scorsa settimana un giudice russo ha condannato Google a pagare 20.000.000.000.000.000.000.000.000.000.000.000 di dollari. (Il Post scrive che sono 20 decilioni perché sono filoamericani e usano la scala corta, dove 1000 milioni sono un bilione; dal mio punto di vista, che come da legge italiana usa la scala lunga e un bilione sono un milione di milioni, si parla “solo” di 20 sestillioni). Come è possibile? Semplice. Le multe di partenza, dovute secondo la legge russa perché Google aveva eliminato dei canali filorussi da YouTube, erano di 1000 dollari circa; ma il dispositivo della legge implicava un raddoppio per ogni settimana di inottemperanza, e a furia di raddoppiare si è arrivati a quella cifra. Non che cambi molto: il massimo che la Russia può fare, se non l’ha già fatto, è bloccare l’accesso a Google nel suo territorio, ma tanto non è che a Mountain View potevano fare soldi con la pubblicità da quelle parti. Diciamo che è solo una questione di principio per far vedere chi ce l’ha più lungo (il foglio di carta dove scrivere il totale, claro).

La cosa che trovo interessante è che i legislatori russi non paiono conoscere la leggenda dell’inventore degli scacchi, che chiese come premio di partire da un chicco di riso sulla prima casella della scacchiera e man mano raddoppiare il numero nelle caselle successive: e dire che questa leggenda è notissima, tanto che anche Dante la cita nella Divina Commedia. In Europa le multe massime vengono calcolate come percentuale del fatturato, e proprio per questo sono molto più preoccupanti per i colpevoli, visto che si sa che possono effettivamente essere richieste. È triste che in una delle nazioni dove nel XX secolo si è fatta più matematica si siano ridotti così.

Ultimo aggiornamento: 2024-11-06 19:37

La scorsa settimana vi ho raccontato della scoperta di un nuovo numero primo di Mersenne. Mi è stato chiesto se queste ricerche servano a qualcosa, anche solo a verificare che le CPU (e ora le GPU) funzionino correttamente.

La risposta, mi spiace dirvelo, è no. Certo, è utile far fare dei conti pesanti a un processore, soprattutto se nuovo: ma innanzitutto non si cercano nuovi record, che sarebbero da verificare indipendentemente, e in secondo luogo conviene computare un po’ di cifre di pi greco, che possono essere statisticamente verificate con la formula BBP. La ricerca di nuovi primi di Mersenne può verificare se ci sono strani scostamenti dalla distribuzione prevista (con una quantità di primi inferiori a n che dovrebbe essere proporzionale a log log n), ma chiunque abbia avuto a che fare con i numeri primi sa che gli scostamenti sono sempre all’ordine del giorno.

E allora perché si cercano questi numeri? Perché ci si diverte a farlo: non credo nemmeno sia per poter dire di avere stabilito un record. Non è poi una delle peggiori cose da fare, secondo me, anche rispetto ad altre ricerche come quella sulla congettura di Goldbach o di quella di Collatz. Poi c’è sempre un certo qual fascino, almeno per me, nel pensare che ci sono strutture (molto ben) nascoste tra i numeri: in fin dei conti è la stessa cosa che abbiamo con i teoremi di incompletezza di Gödel, che ci dicono che se appena cominciamo a mettere un po’ di struttura tra i numeri, nemmeno poi troppa visto che chiediamo solo l’aritmetica di base, la complessità scoppia a punto tale che non possiamo più verificare tutto. Non ci sono dubbi che Gödel fosse un platonista: come è possibile che questa complessità sia solo un prodotto della nostra mente? :-)

Ci sono voluti sei anni e un nuovo algoritmo che sfrutta le GPU, ma lunedì 21 ottobre 2024 il progetto GIMPS ha annunciato che 2^136279841−1 è un numero primo, il 52.mo di Mersenne. Ok, potrebbe essercene qualcun altro, perché non tutti gli esponenti inferiori sono stati testati; ma la cosa è abbastanza improbabile.
I numeri primi di Mersenne si chiamano così perché l’abate Marin Mersenne aveva stilato una lista – non molto precisa, a dire il vero – di quali numeri della forma 2^p−1 sono primi. Perché tanto interesse da parte di Mersenne? Perché se 2^p−1 è primo allora 2^p−1(2^p−1) è un numero perfetto. (Eulero dimostrò poi che tutti i numeri perfetti pari sono di questa forma; nessuno sa se esista un numero perfetto dispari, ma non credo che siano molti i matematici che scommetterebbero sulla sua esistenza). E perché c’è tanto interesse in questi decenni? Perché esiste un algoritmo “relativamente” rapido (di Lucas-Lehmer, dal nome degli scopritori) per verificare se un numero di questo formato è primo. Relativamente rispetto a un numero generico, ovvio: però resta il fatto che se dobbiamo cercare numeri primi grandi tanto vale provare con questi.
E in effetti il GIMPS (Great Internet Mersenne Prime Search, il sito citato all’inizio del post) fa proprio quello. Come dicevo, il vecchio programma Prime95 che era stato quello usato finora per trovare i primi di Mersenne è stato spodestato da un nuovo programma nato per sfruttare le GPU in modo diverso dal fare una ricerca con ChatGPT. Lo scopritore, Luke Durant, è un trentaseienne che ha lavorato in NVIDIA (ma va?) e ha cominciato la sua ricerca solo da un anno, con un cluster di migliaia di GPU sparse su 17 nazioni. Naturalmente la primalità del numero trovato da Durant è stata verificata in modo indipendente da vari programmi diversi tra loro, fatti girare su architetture hardware e tipi di CPU diversa: in questi casi è sempre meglio essere molto attenti a evitare errori invisibili.
Si troveranno altri primi di Mersenne? Chi lo può sapere. Io tra l’altro faccio parte della minoranza convinta che essi siano finiti, anche se non ho nessuna idea di quanti ce ne possano essere…

Un’ultima curiosità: in esadecimale il numero si scrive con un 1 seguito da 34069960 F. Chiaramente tutti i primi di Mersenne sono della forma xFFF…FFF, dove x può valere 1, 3, 7 oppure F.

Mercoledì avevo raccontato di come Ron Graham avesse dimostrato che tutti i numeri maggiori di 77 erano strettamente egizi, cioè possono essere scritti come somma di numeri tutti distinti i cui inversi hanno somma 1. Come l’ha dimostrato? Basta leggere il suo papero, no? Riporto qua il suo ragionamento, che parte dal fatto che D. H. Lehmer aveva dimostrato che 77 non era strettamente egizio.

Graham ha calcolato una tabellona contenente una partizione per ciascun numero da 78 a 166, e ciascun numero dispari da 167 a 333. L’inizio di questa tabella è mostrato in figura. Ma perché proprio questi numeri? Perché gli servivano per costruire tutti gli altri. Per la precisione, chiaramente $\tfrac{1}{2}+\tfrac{1}{2} = 1$. Ma se allora abbiamo una partizione con $1 = \tfrac{1}{d_1} + \tfrac{1}{d_2} + \cdots + \tfrac{1}{d_k}$ e $\sum_1^k d_i = n$, possiamo costruirne una del tipo $1 = \tfrac{1}{2} + \tfrac{1}{2d_1} + \tfrac{1}{2d_2} + \cdots + \tfrac{1}{2d_k}$; tutti i termini sono distinti, perché nessun $d_i$ può essere 1, e la somma dei denominatori è 2$n$ + 2. Questo significa che prendendo i numeri da 78 a 166 nella tabella (l’articolo ha un refuso, tra l’altro) e applicando questo trucco otteniamo tutti i numeri pari da 168 a 334. Quindi sappiamo che tutti i numeri da 78 a 334 sono strettamente egizi. A questo punto Graham, da buon prestigiatore, tira fuori dal cappello un’altra somma che dà $\tfrac{1}{2}$, cioè $\tfrac{1}{3} + \tfrac{1}{7} + \tfrac{1}{78} + \tfrac{1}{91}$. Notate che tutti i denominatori sono dispari tranne il 78, e quindi raddoppiare i denominatori di un numero strettamente egizio non può creare doppioni… E per quanto riguarda il 78, “casualmente” non ci sono denominatori 39 nella tabella e quindi non può essere generato. In questo caso abbiamo che la nuova somma dei denominatori è 2$n$ + 179. Usando entrambe queste formule possiamo ora estendere la nostra tabella da 2·78 + 179 a 2·334 + 2, cioè da 335 a 670; e anche qui continuiamo a non avere denominatori 39 che ci rovinerebbero il gioco. Da qui possiamo estenderla a 1340 (raddoppiando tutti i numeri fino a 670 e notando che i numeri fino a 570 con la seconda formula ci fanno arrivare a 1339) e così via. Quod erat demonstrandum :-)

La dimostrazione non è bella, concordo con voi; la tabella è troppo grande per essere accettabile esteticamente. Ma meglio una tabella e un po’ di teoria che nessun teorema. Tra l’altro, costruire la tabella oggi non sarebbe chissà quale problema, e anzi potremmo facilmente calcolare tutte le possibili partizioni per quei numeri in pochi secondi; ma ricordo che l’articolo è stato pubblicato nel 1963, e anche se Graham lavorava ai Bell Labs che probabilmente aveva computer all’avanguardia non è che ci fosse così tanta potenza di calcolo. Immagino che per parecchi numeri abbia usato la prima delle uguaglianze qui mostrate, e poi abbia usato alcuni trucchi partendo dalle partizioni “piccole”; ma comunque deve essere stato un lavoraccio. Ma ancora peggio deve essere stata la fatica di Lehmer per dimostrare che 77 non era strettamente egizio, visto che in questo caso non si possono trovare controesempi… di quello sì che mi piacerebbe vedere la dimostrazione!

Ultimo aggiornamento: 2024-10-18 14:48

Gli antichi egizi scrivevano i numeri frazionari some somma di frazioni con numeratore 1 e denominatori tutti diversi tra loro: per esempio 5/14 = 1/3 + 1/42 e 9/11 = 1/2 + 1/4 + 1/15 + 1/660. Per scrivere una frazione come egizia si può usare il metodo “greedy”, togliendo a ogni passo la frazione più grande possibile; non è detto però che esso porti alla somma con il minor numero di addendi. L’occhio di Horus, mostrato qui in figura e che magari vi ricorda l’album dell’Alan Parsons Project Eye in the Sky, contiene appunto alcuni geroglifici corrispondenti a frazioni egizie la cui somma è quasi 1. (Il “quasi” è stato completato da Toth, o Hathor secondo altre tradizioni, per mezzo della magia.)

Ma non è direttamente delle frazioni egizie che voglio parlarvi oggi. Luca Rovelli ha scritto di un tema leggermente diverso, ma correlato. Diciamo che un numero è strettamente egizio se può essere scritto come somma di numeri tutti distinti i cui inversi hanno somma 1. Il più piccolo numero strettamente egizio è 11: infatti 1 = 1/2 + 1/3 + 1/6, e 2 + 3 + 6 = 11. Nel 1963 Ron Graham studiò questi numeri e scoprì che esiste un numero finito di numeri che non sono strettamente egizi: il maggiore di essi è 77, e il loro elenco si trova (ovviamente…) su OEIS.

(immagine di Kompak, Benoît Stella e Ignacio Icke da Wikimedia Commons)

Anche gli Accademici di Stoccolma che assegnano i Nobel scientifici seguono spesso le mode, anche se non a livello di quelli del premio per la letteratura che secondo me ogni tanto si divertono. Così quest’anno il premio per la fisica è andato a John Hopfield e Geoffrey Hinton “per le scoperte e invenzioni di base che hanno permesso il machine learning con le reti neurali artificiali”. Ora che l’AI è tornata di moda, evidentemente, anche il comitato ha deciso di salire sul carro del vincitore.

Da un punto di vista genericamente scientifico l’attribuzione ha senso. Dopo l’Inverno dell’Intelligenza Artifiale arrivato alla fine degli anni ’60 quando Minsky e Papert dimostrarono che il percettrone di Rosenblatt non avrebbe mai potuto funzionare in pratica non essendo neppure in grado di calcolare uno XOR, avere il coraggio di proporre un nuovo modello non era facile, soprattutto considerando che non c’erano potenza di calcolo e basi dati di addestramento che permettessero di mettere in pratica la teoria. Quello che io – ma penso anche altri – mi sono chiesto è cosa tutto questo ha a che fare con la fisica, oltre al fatto che Hopfield è fisico. (Hinton nemmeno questo, tra l’altro: ho scoperto che è psicologo con dottorato in intelligenza artificiale, oltre che avere parentele illustri…) E anche il comitato se lo deve essere chiesto, se nella pagina che spiega a noi comuni mortali le loro ricerche cominciano con lo scrivere “I premiati di quest’anno hanno usato strumenti della fisica per costruire sistemi che hanno aiutato a porre le basi per il machine learning oggi così potente”, seguito dal titolone “They used physics to find patterns in information”. Continuando a leggere, scopriamo che il modello di Hopfield parte da un’analogia con i neuroni biologici più precisa di quella di Rosenblatt e poi usa una formula simile a quella usata nel caso di un reticolo di spin, per trovare lo stato di energia minore che dovrebbe corrispondere all’immagine del dataset più vicina a quella distorta fornitagli in fase di test. Il modello di Hinton, invece, ha introdotto lo strato di neuroni nascosti – il vero valore aggiunto rispetto al percettrone – e usato tecniche di massimizzazione dell’entropia per trovare la configurazione più probabile a cui assegnare la figura presentata nei test e non vista in fase di addestramento: non per niente il suo modello si chiama Boltzmann Machine. Hinton ha anche continuato a lavorare per decenni ai suoi modelli, il che gli ha permesso di farli funzionare anche in pratica e non solo in teoria: troppe connessioni infatti confondono il modello; è stato necessario ridurle, non solo per ridurre la quantità di calcoli necessari ma proprio per non rischiare di fissarsi su caratteristiche non importanti delle immagini.

Detto tutto questo, continuo a restare della mia idea: è vero che le idee alla base delle ricerche dei nuovi Nobel arrivano dalla fisica, ma poi di altra fisica non ce n’è molta, e abbiamo più che altro matematica. Ma lasciamo crogiolarsi i fisici al pensiero che sia tutta fisica ;-)

(Ritratti dei Nobel John Hopfield e Geoffrey Hinton di Niklas Elmehed, © Nobel Prize Outreach)