Congettura di Collatz

La congettura di Collatz, conosciuta anche come congettura 3n + 1, la congettura di Ulam o la sequenza di Hailstone o numeri di Hailstone, fu enunciato per la prima volta nel 1937 e riguarda il seguente algoritmo:

1. Si prenda un intero positivo n.
2. Se n è pari, si divida per due; se è dispari, si moltiplichi per 3 e si aggiunga 1.
3. Se n = 1, l'algoritmo termina; altrimenti si ripete dal secondo passo.

O, algebricamente,

   f(n) = n/2,       n=0 (mod 2)
          (3n+1)/2,  n=1 (mod 2)

Per esempio, iniziando con n = 6, otteniamo la sequenza 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 è stata verificata al computer per tutti i numeri fino a 3 × 2⁵³ (circa 2.702 × 10¹⁶), ma non è stata trovata una dimostrazione definitiva. Paul Erdős disse circa questa congettura: "La matematica non è ancora pronta per problemi di questo tipo". Egli offrì 500 dollari per la sua soluzione.

Vi sono alcune argomentazioni euristiche e statistiche che supportano la congettura: se si considerano solo i numeri dispari della sequenza generata dall'algoritmo, si può affermare che in media il successivo numero dispari dovrebbe essere pari a circa i 3/4 del precedente, fatto che suggerisce che essi decrescano fino a raggiungere 1.

A volte il problema è enunciato diversamente. La condizione di terminazione (cioè di fermarsi se n = 1) viene 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 sequenza generata dall'algoritmo raggiunga sempre il ciclo infinito 1, 4, 2, 1, 4, 2...

Vi è un altro approccio per dimostrare la congettura, che considera di percorrere dal basso verso l'alto il grafo di Collatz. Tale grafo è definito da una funzione inversa di quella prima considerata:

           f(n) =  {2n},             n=0 (mod 3)
                   {2n, (2n-1)/3},   n={-1,1} (mod 3)

Studiando il problema da questa prospettiva, il problema si definisce nel modo seguente. La congettura di Collatz si riduce alle due affermazioni:

   *) La funzione invorsa forma un albero, eccezion fatta per il ciclo 1-2.
   *) Tutti gli interi sono presenti nell'albero.

Riferimenti

• Jeff Lagarias: The 3x + 1 problem and its generalizations, American Mathematical Monthly Volume 92, 1985, pp. 3 - 23. Online all'indirizzo http://www.cecm.sfu.ca/organics/papers/lagarias/
• Un progetto di calcolo distribuito verifica la congettura di Collatz per valori sempre più grandi. Online all'indirizzo http://personal.computrain.nl/eric/wondrous/index.html
• La pagina di Wolfram's Mathworld dedicata al problema e alle sue generalizzazioni: http://mathworld.wolfram.com/CollatzProblem.html