La Congettura di Collatz

La Congettura di Collatz (o Congettura $3n+1$), proposta da L. Collatz nel 1937, è uno dei più famosi problemi aperti in Matematica e può essere enunciata in modo straordinariamente semplice come segue.

Si parta da un qualsiasi intero positivo $a_0=n$; dopodiché, se esso è pari si definisce $a_1= n/2$ mentre se è dispari si definisce $a_1=3n+1$. Si applica poi lo stesso procedimento ad $a_1$ ottenendo $a_2$ e così via. La congettura afferma che, qualunque sia l'intero $n$ da cui si parte, la successione definita per ricorrenza in tal modo raggiunge l'intero $1$ dopo un numero finito di passi.

Ad esempio, partendo da $n=12$ si ha $$12, 6, 3, 10, 5, 16, 8, 4, 2, 1,$$ mentre partendo da $n=19$ si ha $$19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.$$ Partendo da $n=27$ sono necessarie ben $111$ iterazioni, e la successione ricorsiva raggiunge $9232$ prima di scendere fino ad $1$:
$$\begin{equation*} \begin{split} & 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, \\ & 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, \\ & 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, \\ & 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, \\ & 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, \\ & 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, \\ & 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, \\ & 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616,  \\ & 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, \\ & 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, \\ & 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1. \end{split} \end{equation*}$$ In generale, il numero di iterazioni necessarie affinché partendo dall'intero positivo $n$ si raggiunga $1$ viene chiamato il "tempo d'arresto di $n$". Pertanto la congettura può essere riformulata dicendo che ogni intero positivo ha un tempo d'arresto finito. I tempi d'arresto dei primi numeri naturali sono tabulati nella successione OEIS A006577:
$$\begin{equation*} \begin{split} & 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, \\ &20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, \\ & 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, \ldots \end{split} \end{equation*}$$ Nonostante essa possa essere facilmente spiegata a qualsiasi bambino delle scuole elementari, la Congettura di Collatz risulta essere un problema straordinariamente arduo, tant'è che lo stesso P. Erdos affermò che "la Matematica attuale, semplicemente, non è ancora pronta per esso".

Le verifiche sperimentali con l'uso del calcolatore mostrano che essa è vera fino a $n=86 \times 2^{70}$; ovviamente, questo non basta per dedurre che essa è vera per ogni valore di $n$, dato che potrebbe esistere un controesempio il cui ordine di grandezza è inaccessibile agli attuali metodi computazionali.

Un intero $n$ potrebbe fornire un controesempio alla congettura di Collatz in due circostanze: se la successione per ricorrenza definita a partire da $n$ diverge all'infinito, oppure se essa entra in un ciclo diverso dal ciclo banale $(4, \, 2, \, 1)$. Come detto, al momento non si sa se ciò possa accadere; tuttavia, grazie al lavoro di vari autori (Steiner, Simons, de Weger, ...) è stato possibile escludere rigorosamente l'esistenza di cicli non banali di lunghezza fino a $68$.

Inoltre, si sa che per "molti" interi positivi l'iterazione effettivamente termina ad $1$. Più precisamente, Krasikov e Lagarias hanno dimostrato nel 2003 che il numero di interi nell'intervallo $[1, \, x]$ aventi tempo d'arresto finito è almeno proporzionale a $x^{0.84}$.