Congettura di Collatz: La Nostra Caccia al Controesempio Raggiunge 2 alla 71!

Un Mistero Matematico Semplice ma Diabolico

Ciao a tutti! Oggi voglio parlarvi di un’avventura affascinante nel mondo della matematica e dell’informatica, un viaggio che ci ha portati ai confini della computazione moderna. Sto parlando della congettura di Collatz. Se non la conoscete, non preoccupatevi, è una di quelle cose ingannevolmente semplici. Prendete un qualsiasi numero intero positivo: se è pari, dividetelo per 2; se è dispari, moltiplicatelo per 3 e aggiungete 1. La congettura afferma che, ripetendo questo processo, finirete sempre per arrivare al numero 1. Sembra facile, no? Eppure, nessuno è mai riuscito a dimostrarlo per tutti i numeri. Il grande matematico Jeffrey Lagarias l’ha definita “un problema straordinariamente difficile, completamente fuori dalla portata della matematica attuale”. E credetemi, aveva ragione!

Noi, però, siamo testardi. E se non possiamo dimostrarla matematicamente (per ora!), possiamo fare la cosa migliore successiva: testarla. Testarla su scala massiccia, spingendo i limiti della verifica computazionale sempre più in là. Il nostro obiettivo? Verificare la congettura per numeri sempre più grandi, nella speranza (forse un po’ folle) di trovare un numero che sfugga alla regola, un “controesempio” che la smentisca, o semplicemente per aggiungere un altro tassello di prova a suo favore. Ebbene, abbiamo una notizia entusiasmante: abbiamo spinto il limite di verifica fino all’incredibile cifra di 2⁷¹!

La Nostra Strategia: Algoritmi e Ottimizzazioni

Come si fa a controllare un numero così astronomico di casi? Non basta un computer potente, serve intelligenza… algoritmica! Siamo partiti da un approccio base, ma ci siamo resi conto subito che dovevamo essere più furbi.

Una prima ottimizzazione, che abbiamo chiamato “Algoritmo 2” nel nostro lavoro precedente, si basa su un trucco: invece di seguire la sequenza direttamente su n, seguiamo una sequenza parallela su n+1, alternando tra le due in modo da usare sempre e solo moltiplicazioni e divisioni per potenze di 2, sfruttando un’operazione chiamata `ctz` (count trailing zeros) per fare più passi in uno. Già questo ci ha dato un bel boost del 36% rispetto all’approccio ingenuo.

Ma non ci siamo fermati qui. Abbiamo introdotto i “setacci” (sieves). L’idea è semplice: se durante il processo un numero n genera un numero m più piccolo di n, e noi stiamo controllando i numeri in ordine crescente, allora quando arriveremo a controllare m, sapremo già che converge a 1 (perché lo abbiamo già verificato o lo verificheremo prima di n). Possiamo quindi “setacciare via” alcuni numeri senza doverli testare completamente.

• Setaccio modulo 3: Abbiamo notato che i numeri della forma 3n+2 vengono sempre generati da un numero più piccolo (2n+1). Quindi, possiamo saltarli a piè pari! Questo elimina il 33.3% dei numeri da controllare.
• Setacci 3^k: Abbiamo esteso l’idea a potenze superiori di 3. Con un setaccio 3² (modulo 9), eliminiamo il 44.44% dei numeri. Oltre, però, il guadagno diventa minimo.
• Setacci 2^k: Questa è stata la vera svolta. Sfruttando una formula generale dell’iterazione di Collatz, possiamo pre-calcolare il risultato di k passi contemporaneamente basandoci solo sui k bit meno significativi del numero. Abbiamo creato delle enormi tabelle (setacci) che ci dicono se un numero, in base ai suoi ultimi bit, converge rapidamente o si unisce al percorso di un numero più piccolo. Questo ci permette di scartare o verificare blocchi enormi di numeri in un colpo solo!

Questi setacci 2^k sono potentissimi, ma hanno un costo: la memoria. Il setaccio ottimale per la CPU (k=34) richiederebbe 2 Gigabyte! Fortunatamente, abbiamo scoperto che questi setacci sono molto ripetitivi. Contengono solo una cinquantina di pattern di 64 bit che si ripetono costantemente. Comprimendoli usando degli indici, abbiamo ridotto drasticamente l’occupazione di memoria e disco, rendendo fattibile la loro distribuzione.

L’Armata dei Supercomputer Europei

Avere algoritmi veloci è fondamentale, ma per raggiungere 2⁷¹ serve una potenza di calcolo mostruosa. Qui entra in gioco il nostro sistema di calcolo distribuito. Abbiamo creato un’architettura client-server che coordina migliaia di “lavoratori” (workers) sparsi su alcuni dei più potenti supercomputer d’Europa:

• MetaCentrum: L’infrastruttura distribuita della Repubblica Ceca.
• IT4Innovations: Sede del supercomputer Karolina, sempre in Repubblica Ceca.
• LUMI: Uno dei supercomputer più potenti del mondo, situato in Finlandia.

Il nostro server centrale assegna piccoli intervalli di numeri (chiamati “work units”, tipicamente di dimensione 2⁴⁰) ai client che girano sui nodi di calcolo. Ogni client poi lancia i workers, che possono essere processi CPU o processi che sfruttano la potenza delle schede grafiche (GPU) tramite OpenCL (supportiamo sia NVIDIA che AMD). Ogni worker esegue i nostri algoritmi ottimizzati sul suo pezzetto di numeri, calcola un “checksum” (una prova del lavoro svolto) e rileva il valore massimo raggiunto durante il calcolo, poi comunica i risultati al server.

Questo sistema ci ha permesso di orchestrare un esercito computazionale. Pensate che abbiamo consumato l’equivalente di 12.395 anni di CPU e 159 anni di GPU! Le GPU, in particolare, si sono rivelate delle bestie: la nostra implementazione ottimizzata per GPU è circa 52 volte più veloce della migliore implementazione per CPU.

Risultati: Oltre 2⁷¹ e Nuovi Record di Percorso

E così, pezzo dopo pezzo, work unit dopo work unit, abbiamo scalato la montagna dei numeri. Al momento in cui scrivo, abbiamo verificato la convergenza della congettura di Collatz per tutti i numeri interi positivi fino a 2⁷¹ (che è 2048 volte 2⁶⁰). Un nuovo traguardo nella storia di questa affascinante sfida!

Durante questa immensa caccia, non abbiamo trovato il tanto agognato controesempio (la congettura resiste!), ma abbiamo scoperto qualcos’altro di interessante: i record di percorso. Un numero è un record di percorso se la sua sequenza di Collatz raggiunge un picco più alto di qualsiasi numero precedente. Ne abbiamo trovati ben cinque nuovi! Eccoli (sono numeri belli grossi):

• 274.133.054.632.352.106.267
• 1.378.299.700.343.633.691.495
• 1.735.519.168.865.914.451.271
• 1.765.856.170.146.672.440.559
• 2.358.909.599.867.980.429.759

Questi risultati sembrano confermare una previsione teorica secondo cui l’altezza massima raggiunta da un record di percorso n cresce all’incirca come n².

Il Viaggio Continua (e il Codice è Open Source!)

Questa è stata un’impresa enorme, un mix di matematica, ottimizzazione software e gestione di infrastrutture di calcolo su larga scala. Il miglioramento complessivo delle prestazioni, dal nostro primo algoritmo su CPU al nostro ultimo su GPU, è stato sbalorditivo: un fattore di 1.335 volte!

Siamo entusiasti di aver spinto il limite a 2⁷¹, ma la congettura di Collatz rimane lì, irrisolta e sfidante. Chissà cosa ci riserva il futuro? Magari un giorno qualcuno troverà la dimostrazione, o forse il controesempio si nasconde ancora più in là, a numeri ancora più inimmaginabili.

Nel frattempo, per permettere ad altri ricercatori e appassionati di unirsi alla caccia o di costruire sul nostro lavoro, abbiamo reso tutto il software utilizzato in questo progetto open source. La conoscenza è fatta per essere condivisa!

È stato un viaggio incredibile finora, e anche se non abbiamo risolto l’enigma, abbiamo dimostrato fin dove possiamo spingerci con la tecnologia e l’ingegno umano per esplorare questi misteri matematici. E chissà, forse il prossimo record sarà ancora più strabiliante!

Fonte: Springer