[Will it ever Stop, SPOJ][1]
In this problem, the given program will stop only for powers of 2 and for any other n, it will first reach 3 and from there it goes in infinite loop(as operating 3 in program will again give 3).
BUT HOW TO PROVE THAT.
[1]: http://www.spoj.com/problems/WILLITST/
The only step available to reduce a number is n \rightarrow n/2 when n is even. Clearly if n = 2^k then n is repeatedly halved by this step until it equals 1. However the other step is n \rightarrow 3 (n + 1). So if this step is carried out even once the new value is a multiple of 3. From there it can take either step but a it remains a multiple of 3. Thus it can never reach the form 2^k which means it will never reduce to 1.
That’s a harder task. All numbers which are not of the form 2^k lead to some other number and we know it doesn’t stop. That means there are 2 options for such a number: either it keeps increasing forever or it enters a loop.
3 \rightarrow 12 \rightarrow 6 \rightarrow 3 is a loop. If it can be proved that a) no number increases forever, and b) there are no other loops, then we can conclude that every number eventually reaches 3.