Amateur's take on "3x+1 Problem" (Part 1)

Recently Amateur encountered a new problem stated as:

• Determine whether the following program segment will terminate;

while(x>1) {
if(x is even)
x = x/2
else
x = 3*x+1
}

So Amateur being a true amateur thought that its very simple! If the input value of x is a power of 2 then this program will terminate!! hooray! For the given problem Amateur is correct? NO! Because even though x is not a power of 2 the program segment will terminate.

He didn't realize that even though the input value of x is not a power of 2, it may become a power of two at some point of time during the execution as the step x = 3x+1 will change the value of x to some other value.
Now he knows that he was wring so he wants to know more about this problem, and searches on Google for this problem and knows that this is a very famous problem and known as "3x+1 problem". He also came to know that this problem has a big problem of complexity as to approximately how many steps it takes to terminate the above segment.
So he decides to give it a try on a weekend and surprisingly he found this weekend suitable to give it a try!
He started it by doing it on paper and soon he realized that it takes so many steps for even small values of x! Some statistics would be convincing:
x ==> Number of Steps Required to terminate
2 ==> 1
3 ==> 7
4 ==> 2
5 ==> 5
6 ==> 8
7 ==> 11
8 ==> 3
...
...
...
31 ==> 101!
by this time looses his patience and decides to make some observations from this sample set.
A few observations are;

1. A lot of computations are repetitive, e.g. for x = 6, from the second step onwards it recomputing the steps computed for x =3, and same for x = 10, 12, 14, so on (correct observation but not much useful as he believes approach may not be useful for this problem otherwise wouldn't they have solved it earlier?)
   
2. In this one he goes a little over board and makes an observation that's hard for him to key-in (but let's see how he fares) The predecessors of the values that are powers of two (e.g. predecessor = 3 for x =4 or predecessor =7 for x =8) have some patterns in their behavior:

a) only these predecessors take the most number of steps to terminate the segment (but alas! he has to be wrong, as soon he realizes that steps required for value 9 are more than those required for value 15. Hmmm first disappointment)

b) Two consecutive predecessors (for values greater than 4) follow a pattern that is, the predecessor value takes only one less step to terminate than the successive predecessor value. e.g. for predecessor = 7, the steps required are 11 and for predecessor = 15, the steps required are 12

c) He also finds that except for predecessor 3, all other predecessors at some point of time come down to value 5 (Now for these observations he is correct! But alas! He has to be wrong as he doesn't know what to do with these observations as they seem to be of no use to find the correct answer).

So this is the status of Amateur on this problem, now he is just executing the program on his machine to see if there is any pattern among the values with maximum corresponding steps for set of values between two values that are power of 2.
As of now about 4*10^7 values have been tried...