3n+1 parte 1 - Chicchi di grandine

Considera un numero naturale $n$. Se è pari, dimezzalo; se è dispari, triplicalo e aggiungi $1$. Ad esempio, con $n=13$ calcoliamo $13\cdot3+1=40$. Continua in questo modo: nel nostro caso, si otterrà $40:2=20$, poi $20:2=10$, e in seguito $5$ (che è dispari), e poi $3\cdot5+1=16$, e poi $8$, $4$, $2$, $1$, e in seguito il loop $4$, $2$, $1$ si ripeterà all'infinito.

Riproviamo partendo da 100: otteniamo 100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Partendo da 27, invece, si ricava una sequenza molto più lunga: 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. Di nuovo, giungiamo al loop 4, 2, 1, 4, 2, 1, ...

Apparentemente, non esistono valori naturali iniziali che non conducono a 1: nessuna successione di questo tipo divergerà verso valori sempre più grandi, o presenterà comportamenti ciclici diversi da quello presentato. Si suppone pertanto che sia sempre così, ma nessuno lo ha ancora dimostrato: si tratta dell'enunciato della Congettura 3n+1, formulata dal matematico tedesco Lothar Collatz nel 1937, un problema aperto, piuttosto noto ma forse un po' "di nicchia" rispetto a congetture più celebrate. Esso riguarda il comportamento delle successioni $(a_i)$ ottenute a partire da un valore $a_0\in\mathbb N$ iterando la funzione

$$
c(n)=
\begin{cases}
3n+1 &,\,n\;\text{dispari} \\
\frac12 n &,\,n\;\text{pari} \end{cases} $$ 

Dal momento che per $n$ dispari $3n+1$ è sempre pari, a volte per proseguire più speditamente si preferisce porre direttamente $f(n)=\frac{3n+1}{2}$ per $n$ dispari.

A tali successioni viene spesso attribuito il suggestivo nome di hailstone sequences, siccome i loro termini sono soggetti a repentine ascese e discese, come i chicchi di grandine nella tempesta, come evidenziano ad esempio le rappresentazioni grafiche per $a_0=1000$:

 oppure per $a_0=1001$:

Ho sentito parlare per la prima volta della Congettura di Collatz (nota anche con altri nomi: Congettura di Ulam, Problema di Syracuse, Problema di Kakutani, ...) nell'ambito di un corso all'ETH, dove ci era stato chiesto di calcolarne i termini con l'aiuto di Mathematica (si tratta di un problema che pure io pongo, al Liceo, introducendo Maple o Excel). A colpirmi fu l'apparente semplicità della sua formulazione a fronte della sua difficoltà, un aspetto di molti problemi celebri che fu determinante nella mia scelta di orientarmi verso la teoria dei numeri.

La Congettura ammette una generalizzazione immediata all'insieme $\mathbb Z$. Qui, però, le cose si fanno un pochino più complicate: infatti sono stati identificati altri tre cicli possibili oltre a 1, 4, 2, 1. Il primo è breve: -1, -2, -1; il secondo è un po' meno breve: -5, -14, -7, -20, -10, -5; il terzo è decisamente più lungo: -17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34, -17. Non se ne conoscono altri, e si congettura che non ve ne siano. 

Sulla Congettura di Collatz in rete si trova parecchio. Segnalo in particolare quattro lavori del matematico statunitense Jeffrey Lagarias: due papers introduttivi (qui e qui) e una imponente bibliografia ragionata in due parti (qui e qui).