thf (07/18/82)
Does anyone know whether the following famous problem due to Collatz has been solved? For a positive integer n let f(n) = n/2 if n is even and 3n+1 if n is odd. Show that for each n there exist a k such that the k-th iterate of f applied to n is 1. example: f(5) = 16, f(f(5)) = 8, f(f(f(5))) = 4, f(f(f(f(5)))) = 2, f(f(f(f(f(5))))) = 1, so k = 5 in this case. The book Fundamentals of Data Structures by Horowitz and Sahni has this as problem 29 in chapter 1 (with a hint to use induction) which would lead me to believe that the problem has been solved. another recent source says that for n<2^50 it is known to be true.