Sequenza di Collatz (3n+1)

La sequenza di Collatz, o problema 3n+1, e definita dalla seguente regola iterativa: dato un intero positivo n, se n e pari si pone n -> n/2; se n e dispari si pone n -> 3n+1. La congettura di Collatz afferma che, partendo da qualsiasi n, la sequenza raggiunge sempre 1 dopo un numero finito di passi.

Definizione formale

f(n) = n/2 se n pari, f(n) = 3n+1 se n dispari. La sequenza di Collatz da n_0 e n_0, n_1 = f(n_0), n_2 = f(n_1), .... Esempio n=6: 6, 3, 10, 5, 16, 8, 4, 2, 1 (8 step). Esempio n=27: 27, 82, 41, 124, 62, ..., 9232 (max), ..., 1 (111 step).

Congettura di Collatz

Lothar Collatz (1937, Sina): per ogni n >= 1, la sequenza definita da f raggiunge sempre 1 in numero finito di passi. Conosciuta anche come problema 3n+1, problema di Ulam, problema di Kakutani, sequenza siracusana. Erdos: "La matematica non e ancora pronta per questo problema. Forse non lo sara mai." Erdos offri 500 dollari per dimostrazione.

Verifica empirica

La congettura e stata verificata computazionalmente per tutti gli n < 2^68 ~ 2.95 * 10^20 (Tomas Oliveira e Silva, Roosendaal, 2020). Tuttavia evidenza numerica non e dimostrazione: anche se vera per primi miliardi di numeri, potrebbe fallire per qualche enorme contro-esempio. Storicamente, congettura di Polya su somme di cifre fallita a 906 milioni; congettura di Mertens fallita a 10^14.

Tempi di arresto

• Tempo di arresto totale: numero di iterazioni per raggiungere 1.
• Tempo di arresto: primo step k in cui n_k < n_0.
• Per n=27: tempo arresto totale = 111, tempo arresto = 96 (primo n_k < 27).
• Asintotica media: tempo arresto totale ~ (2 / (3 ln 4 - 4 ln 3)) ln(n) ~ 6.95 ln(n) (heuristica).

Numeri record

Numeri n con tempo di arresto totale maggiore di tutti gli n' < n. Sequenza OEIS A006877: 1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, ... Tempi corrispondenti A006878: 0, 1, 7, 8, 16, 19, 20, 23, 111, 112, ...

Massimi raggiunti

n_max = max sequenza partendo da n. Per n = 27: n_max = 9232 (~ 342 * n). Per n = 703: n_max = 250504 (~ 356 * n). Per n = 27027: n_max = 21896664. La crescita massima sembra ~ n * (qualche valore fluttuante), suggerendo comportamento "casuale" nella struttura della sequenza.

Aspetti probabilistici

Per un n random, la sequenza ha aspetti casuali. Heuristica probabilistica: ad ogni passo, la probabilità di raddoppiare e ~ 1/2 (passo dispari -> 3n+1 ~ n*3, ma poi diviso per 2 più volte). Risultato: media geometrica per ciclo dispari -> pari -> ... e (3/2)^(1/2) * (1/2)^... ~ 0.75. Quindi sequenza decresce in media. Spiega euristicamente perché tutti raggiungono 1.

Generalizzazioni

• Variante 5n+1: sequenza può crescere illimitatamente (es. n=7 cicla).
• Variante 7n+1: comportamento diverso, alcuni cicli.
• Cicli generalizzati: oltre 1 -> 4 -> 2 -> 1, esistono altri cicli per Collatz? Aperta.
• Collatz su Z (interi negativi): cicli noti su -1, -5, -7, -17.
• Collatz polinomiale, Collatz su Q[x]: studi recenti.

Risultati parziali

• Terras (1976): quasi tutti gli n hanno tempo arresto < n^(0.869).
• Krasikov-Lagarias (2003): densità 0 per "non-converge".
• Tao (2019): "quasi tutte" le orbite di Collatz raggiungono valori arbitrariamente piccoli (o(N) eccezioni in [1, N]).
• Conway (1972): generalizzazione mostro problemi di Collatz indecidibili in ambiti astratti.

Applicazioni

• Teoria dei sistemi dinamici: dinamiche non-lineari su Z.
• Teoria della complessità: comportamento "imprevedibile" di funzioni semplici.
• Algoritmi e benchmark: test di processori (sequenze profonde).
• Educazione matematica: introduzione a problemi aperti.
• Crittografia teorica: hash-functions basate su Collatz (sperimentale).

Storia

Lothar Collatz (1937): introduce il problema studi su grafi diretti. Stanislaw Ulam, Bryan Thwaites lo riscoprono indipendentemente. Helmut Hasse, Shizuo Kakutani contribuiscono. Coxeter, Erdos diffondono. Lagarias (1985) review classica. Oliveira e Silva (2008-2020) verifica computazionale fino 2^68. Tao (2019) miglior risultato parziale.

Modalita del calcolatore

Cinque modalita: sequenza completa, tempo di arresto totale, valore massimo raggiunto, lista numeri record, verifica congettura per range [1, n]. Limite n <= 10^9 per calcolo veloce.

Perche in generale e indecidibile: le funzioni di Conway

Una delle ragioni profonde per cui la congettura di Collatz resiste e che una sua naturale generalizzazione e dimostrabilmente indecidibile. Nel 1972 John Conway studio le funzioni di tipo Collatz generalizzate, in cui il moltiplicatore e l'addendo dipendono dal resto di n modulo un intero fissato. Conway dimostro che tali mappe possono simulare qualsiasi macchina di Turing: il suo linguaggio FRACTRAN, basato proprio su iterazioni di questo tipo, e Turing-completo.

Ne segue che non puo esistere un algoritmo generale che, data una funzione di tipo Collatz, decida se tutte le orbite raggiungono 1: sarebbe equivalente a risolvere il problema dell'arresto, notoriamente indecidibile. Questo non dimostra che il caso specifico 3n+1 sia indecidibile, ma spiega perche gli strumenti generali falliscano: il problema di Collatz vive al confine fra teoria dei numeri, sistemi dinamici e calcolabilita, dove piccole variazioni delle regole producono comportamenti arbitrariamente complessi.

Il risultato di Tao (2019) e la struttura 2-adica

Il progresso piu significativo verso la congettura e arrivato nel 2019 da Terence Tao, che dimostro un enunciato molto vicino: quasi tutte le orbite di Collatz raggiungono valori arbitrariamente piccoli. Piu precisamente, per quasi ogni n (nel senso della densita logaritmica) la sequenza scende sotto qualsiasi funzione che tenda all'infinito, per quanto lentamente. Non e la congettura completa, ma il piu forte risultato statistico noto, ottenuto con tecniche di teoria della probabilita applicate alle iterazioni.

Un punto di vista fecondo considera la mappa 3n+1 come un sistema dinamico sugli interi 2-adici, dove la struttura di divisibilita per due diventa geometria naturale. In questa cornice le iterazioni assomigliano a un cammino aleatorio con deriva negativa: in media ogni passo moltiplica il numero per circa 3/4, suggerendo la discesa verso 1. Ma "in media" non basta a garantire che nessuna orbita sfugga, ed e proprio questo salto dal probabilistico al certo il cuore ancora irrisolto del problema.

Aggiornato a luglio 2026