Congettura di Collatz

Scritta come applicazione, la regola della congettura di Collatz è

Un volo parte da $n$, passa per $f(n)$, $f(f(n))$ e così via, e termina quando raggiunge 1, perché da lì percorrerebbe soltanto il ciclo 1 → 4 → 2 → 1. La congettura afferma che ogni intero positivo ci arriva. Qui puoi far volare interi, anche di centinaia di cifre, da soli o in gruppo. Puoi confrontarli con il ragionamento approssimativo che rende la congettura così plausibile e vedere perché quel ragionamento non è una dimostrazione.

L’asse orizzontale indica il numero di passi, quello verticale il valore, su scala logaritmica a meno che tu non scelga Lineare, che dà il consueto disegno a chicchi di grandine. Ogni numero del gruppo è una linea colorata, quindi un tratto percorso da molti numeri ha una colorazione più intensa: più luminosa su sfondo scuro, più scura su sfondo chiaro. Il numero osservato è evidenziato, con un punto rosso nella sua posizione attuale. I voli sono difficili da prevedere: 27 sale fino a 9 232 e richiede 111 passi per arrivare a 1, mentre a 28 ne bastano 18.

Perché ci si crede? Un passo dispari dà sempre un numero pari, quindi raggruppiamolo con il dimezzamento successivo in un unico passo abbreviato. Supponiamo ora che le parità di questi passi siano lanci indipendenti di una moneta equa. Metà delle volte $n$ viene moltiplicato per circa 3/2 e metà per 1/2, quindi in media un passo abbreviato modifica $\ln n$ di

I numeri dovrebbero allora diminuire, tipicamente diventando i 3/4 del valore precedente ogni due passi abbreviati. Sull’asse logaritmico, questa deriva è la linea tratteggiata, disegnata per un gruppo di Grandezza simile di almeno 100 numeri. Non tiene conto dell’atterraggio: i numeri che raggiungono 1 restano a terra, perciò verso la fine l’altezza media del gruppo su questo asse scende più lentamente della linea.

I lanci di moneta sono solo un modello del comportamento medio dei numeri. La congettura riguarda ogni intero positivo: un solo volo che non raggiungesse mai 1 basterebbe a smentirla.

I numeri negativi mostrano ciò che sfugge al ragionamento. La stessa regola produce cicli anche su di essi, e se ne conoscono tre, come −5 → −14 → −7 → −20 → −10 → −5. Il modello della moneta prevede una diminuzione anche lì, eppure un giro completo di qualunque ciclo modifica $\log|n|$ di esattamente 0. Una deriva media verso il basso non può escludere un ciclo, nemmeno tra i numeri positivi.

Corallo inverte i voli: crescendo a ritroso da 1, i percorsi di un gruppo formano un albero. Ogni arco ruota rispetto al precedente di $+\alpha$ se il nuovo numero è pari, e di $-\alpha \log_2 3$ se è dispari; α si imposta con Curvatura. Risalendo da 1, un passo pari raddoppia il numero e aumenta il suo $\log_2$ di 1, mentre un passo dispari lo diminuisce di poco più di $\log_2 3$. L’arco che arriva a n ha quindi ruotato complessivamente di $\alpha \log_2 n$ rispetto alla verticale verso l’alto, più un piccolo contributo per ogni passo dispari: la rotazione registra la grandezza di n. Lungo un ramo, la direzione sale e scende con i numeri di un volo, quindi ogni ramo è un volo arrotolato. I rami si uniscono dove i voli si incontrano. In questi termini, la congettura dice che l’albero cresciuto da 1 contiene ogni intero positivo.

Il problema viene generalmente attribuito a Lothar Collatz, che pose domande di questo tipo negli anni Trenta. Il corallo segue la «Collatz seaweed» di Edmund Harriss (2016).