LA CONGETTURA DI COLLATZ

La congettura di Collatz (anche chiamata problema 3n + 1), come tutte le congetture, è un enunciato che i singoli esempi mostrano essere vero in particolare, ma che ancora non è stato dimostrato in generale. 

Deve il suo nome al matematico Lothar Collatz che l'ha teorizzata nel 1937 ed è uno dei problemi più interessanti ancora aperti della Teoria dei Numeri.

Ogni naturale, grazie a questo algoritmo, genera via via, a ogni passo, una propria sequenza di naturali.

Per esempio:  

Le sequenze che l'algoritmo genera sono difficilmente previdibili, senza calcolarle: non è cioè facilmente prevedere né a quali numeri conduca un numero scelto in partenza né quanto sia lunga la sequenza. Quest'ultima non è, ad esempio, proporzionale alla grandezza del numero iniziale, cioè non è detto che, dati 2 naturali, al minore corrisponda la sequenza più corta fra le 2 e al maggiore quella più lunga. 

Controesempio: 6 < 8, ma la sequenza di 6 è più lunga della sequenza di 8 (9 passi > 4 passi)

Inoltre, i naturali di partenza possono avere o meno una parte finale della sequenza in comune con altri, come si vede in questo grafo, ma anche questo è difficilmente prevedibile.

CONGETTURA DI COLLATZ: per ogni numero naturale n la sequenza dell'algoritmo ha una lunghezza finita (cioè un numero finito di passi) e termina con il naturale 1 (da cui poi il ciclo 4 → 2 → 1 ).