Il grid computing e la “Congettura di Collatz”

Questa mattina mio fratello @lezard valeth impazzendo tra un calcolo algebrico e l’altro, mi ha segnalato un’ottima iniziativa nata presso il Collegio Superiore del dipartimento di Matematica di Alma Mater Studiorum di Bologna. Quale migliore occasione per scrivere il mio primo articolo ed il seguente, usuale, martirio?

La Congettura di Collatz e l’idea dietro al progetto

Lothar Collatz, matematico tedesco deceduto nel 1990, è stato un luminare nella sua disciplina, formulando più teorie e collaborando con i più noti matematici della sua epoca. Uno dei suoi lasciti più famosi è la congettura che porta il suo nome.

Nel 1937, Lothar Collatz pone la sua congettura al mondo matematico, inserendosi nella parte cosiddetta “teoria dei numeri”, ma nonostante vari tentativi, tutt’ora rimane indimostrata.

Si scelga un qualsiasi numero naturale n maggiore di 1. Se è dispari moltiplicarlo per 3 e aggiungere 1, se invece è pari dividerlo per 2. Applicare di nuovo questo procedimento al numero ottenuto, e così via.
La congettura di Collatz prevede che, continuando ad applicare questo algoritmo, prima o poi si arriverà ad 1; l’insieme dei numeri ottenuti è detto “Catena di Collatz di inizio n”.
Ad esempio:
n = 3
3 è dispari → 3 * 3 + 1 = 10.
10 è pari → 10/2 = 5 → 5 * 3 + 1 = 16/2 = 8 → 8/2 = 4 → 4/2 = 2 → 2/2 = 1
Ovviamente questa è una catena molto semplice, ma basta arrivare al numero 27 per trovare delle difficoltà:
27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → […] → 5 → 16 → 8 → 4 → 2 → 1

Essendo appunto una congettura, è un teorema che si suppone sia corretto ma non dimostrato formalmente.

CollatzNet – Computing to infinity and beyond

Con l’obiettivo di effettuare una verifica su larga scala, nel tentativo di individuare un controesempio falsificando la congettura ma non avendo a disposizione un supercomputer per poter calcolare in breve tempo, questi studenti di Matematica hanno ideato CollatzNet.

Direttamente dalla fonte:

L’obiettivo di questo progetto è raggiungere e superare l’attuale record di verifica della Congettura di Collatz attraverso la congiunta potenza di calcolo dei personal computer dei nostri utenti. Questo progetto di Grid Computing (rete di calcolo distribuito) è stato realizzato da un gruppo di studenti del Collegio Superiore dell’Alma Mater Studiorum di Bologna. La crescente potenza di calcolo dei computer di fascia commerciale, unita alla capillarità di internet di uso domestico, rende sempre più naturale la scelta del background computing come soluzione a grandi problemi computazionali: dividendo il problema in “work unit” facilmente trasferibili via internet da distribuire su un gran numero di personal computer, questi potranno processarle mediante un semplice client attingendo alle idle resources del computer, ossia il tempo macchina inutilizzato che quotidianamente viene sprecato da computer accesi e lasciati inoperativi, o utilizzati per compiti poco intensivi.

Che siate appassionati di matematica o meno, mi sembra un’iniziativa lodevole, nonché una buona trovata.

Cercando di rendere il tutto più agevole a chiunque voglia dare il proprio contributo, sono disponibili i pacchetti per i sistemi operativi più utilizzati, nonchè i codici sorgenti per chiunque ne abbia bisogno. (Il pacchetto per Windows funziona su tutti i sistemi a 32bit, anche se dall’impaginazione del sito sembra sia disponibile solo la versione a 64)

Approfondimenti:
CollatzNet
Lothar Collatz su wikipedia(inglese)
Articolo sulla congettura di Collatz a cura di Ryan Vespucci su LN