Il problema del 3x+1

Se x è un intero positivo, definiamo la funzione f(x) nel modo seguente: se x è pari f(x)=x/2, altrimenti (cioè se x è dispari), f(x) = 3x+1.
La scrittura fn(x) sta per f(f(f...(f(x)...)) [con n f, cioè abbiamo applicato n volte f]. Per esempio f3(3) = f(f(f(3))). Abbiamo f(3) = 10. Quindi f(f(f(3))) =f(f(10)). Abbiamo f(10) = 5.Quindi f(f(10)) = f(5) = 16.
Problema del 3x+1: Dimostrare che per ogni x, esiste n tale che fn(x)=1.
In altre parole si tratta di dimostrare che per ogni intero x, iterando la funzione f descritta qui sopra, si arriva sempre a raggiungere 1.
Il problema è stato, ovviamente, testato al computer e si è verificato che per n molto grande (quanto esattamente, non saprei) la risposta è affermativa: cioè dopo un certo numero di iterazioni si raggiunge sempre 1.
Nella tabella qui sotto riportiamo i dati relativi ad alcuni valori di x.
x=2,3,4,5,6,7,8,9,10,21,43
it=1,7,2,5,8,16,3,19,6,7,29
(it = il numero di iterazioni della funzione f necessarie per raggiungere 1)
Provare per credere!

Il programma, molto semplice, è basato su un loop:
Mentre (n non è uguale a 1), allora n diventa: n/2 se n è pari, 3n+1 altrimenti.
Codice in Java:

    while(n != 1){
    	if(n%2 == 0){n = n/2;}
    	else{n = 3*n+1;}
    	}

Siccome confidiamo di raggiungere 1, il programma termina (se non è così, forse avete trovato un contr'esempio; questo, però, è molto improbabile: il problema del 3x+1 è già stato verificato per valori molto garndi di n).