Avete presente il problema del 3n+1?
La funzione T(n) è definita come
T(n)= (3n+1)/2 se n=1 mod 2
T(n)=n/2 se n=0 mod 2.
(Alternativamente per n dispari invece che con (3n+1)/2 a volte si definisce T(n)=3n+1).
Se col simbolo Tk(n) intendiamo la funzione T(n) iterata k volte,
la sequenza (n,T(n), T2(n), T3(n)...) è chiamata la traiettoria di n.
Il tempo totale di fermata (chiamato anche lunghezza del ciclo) s(n) è definito come il minor intero positivo k per cui Tk(n)=1.
Per esempio la traiettoria di 22 è 22 11 17 26 13 20 10 5 8 4 2 1, così s(22)=12.
La congettura di Collatz dice che per ogni interno n>=2 s(n) è finito, ossia la traiettoria è convergente.
Bene io volevo sapere se siano conosciuti limiti superiori o inferiori su s(n).
Anche con argomenti informali o euristici...
Il problema 3n+1 (Collatz)
Beh,il limite superiore (finito) non credo qualcuno l'abbia trovato 
,altrimenti costui avrebbe anche dimostrato la congettura 
.Per quanto riguarda il limite inferiore,invece,io dico $ log_2(n)+1 $.L'algoritmo di Collatz infatti termina il più rapidamente possibile quando n è una potenza di due.Comunque è possibile che il lower bound si possa migliorare con una stima che si riduca poi a $ log_2(n)+1 $ quando $ n $ è una potenza di due.Magari vedo di lavorarci sopra.
,altrimenti costui avrebbe anche dimostrato la congettura .Per quanto riguarda il limite inferiore,invece,io dico $ log_2(n)+1 $.L'algoritmo di Collatz infatti termina il più rapidamente possibile quando n è una potenza di due.Comunque è possibile che il lower bound si possa migliorare con una stima che si riduca poi a $ log_2(n)+1 $ quando $ n $ è una potenza di due.Magari vedo di lavorarci sopra.è ovvio che il limite superiore non è stato trovato però mi interessavano anche limiti superiori con argomenti euristici o probabilisticiIgor ha scritto:Beh,il limite superiore (finito) non credo qualcuno l'abbia trovato
