La congettura di Collatz è una congettura matematica tuttora irrisolta. Fu enunciata per la prima volta nel 1937 da Lothar Collatz, da cui prende il nome. Paul Erdős disse, circa questa congettura, che «la matematica non è ancora matura per problemi di questo tipo» e offrì 500 dollari per la sua soluzione. La congettura riguarda il seguente algoritmo: 1. Si prenda un intero positivo n. 2. Se n = 1, l’algoritmo termina. 3. Se n è pari, si divida per due; altrimenti si moltiplichi per 3 e si aggiunga 1. È possibile formare una successione applicando la funzione ripetutamente, prendendo come primo elemento un qualunque intero positivo e, ad ogni passaggio, applicare la funzione al risultato precedente. Per esempio, iniziando con n = 6, otteniamo la successione 6, 3, 10, 5, 16, 8, 4, 2, 1. La congettura di Collatz asserisce che questo algoritmo giunge sempre a termine, indipendentemente dal valore di partenza. La congettura risulterebbe quindi falsa se esistesse una successione che non contiene il numero 1; ciò potrebbe voler dire un ciclo che si ripete senza mai dare 1, oppure una successione illimitata superiormente. A volte il problema è enunciato diversamente. La condizione di terminazione (cioè di fermarsi se n = 1) è rimossa dalla congettura, in modo che la sequenza non termini mai. Enunciando il problema in questo modo, la congettura di Collatz diventa l’affermazione che la successione generata dall’algoritmo raggiunga sempre il ciclo infinito 1, 4, 2, 1, 4, 2 eccetera. Vi è un altro approccio per definire la congettura, approccio che considera di percorrere dal basso verso l’alto il grafo di Collatz. Tale grafo è definito da una «funzione inversa» di quella prima considerata. Studiando il problema da questa prospettiva, il problema si definisce nel modo seguente. La congettura di Collatz si riduce alle due affermazioni: i) la funzione inversa forma un albero, eccezion fatta per il ciclo 1-2-4; ii) tutti gli interi sono presenti nell’albero. Nonostante la congettura non sia stata provata, la maggioranza dei matematici che se ne sono occupati pensa che la congettura sia vera. All’inizio degli anni trenta, Lothar Collatz, uno studente dell’università di Amburgo, si occupava della teoria dei numeri e della teoria dei grafi. Partiva da un numero intero positivo, gli applicava un algoritmo iterativo, tracciava i grafi associati e si poneva domande ancora senza risposta. Il matematico tedesco Helmut Hasse, amico di Collatz, diffuse il problema, noto anche con il nome algoritmo di Hasse. Poiché Hasse presentò il problema negli anni cinquanta durante una visita all’università di Syracuse, propose di battezzarlo problema di Syracuse. Il matematico polacco Stanisław Ulam fece circolare l’algoritmo al Los Alamos National Laboratory, dove lavorava durante la seconda guerra mondiale. Per questo il problema è anche noto con il nome problema di Ulam. Negli anni sessanta, Shizuo Kakutani si interessò nuovamente al problema, anche chiamato problema di Kakutani.