1994-1995 ACM International Collegiate Programming Contest
Ulam One of the most famous problems in number theory is
Ulam's conjecture (but it is known under many other names as well). Ulam's
conjecture states that if you start with any natural number, and at each step
divide it by 2 (if even) or multiply it by 3 and add 1 (if odd), you will get to
To test this hypothesis, we have written a flashy program, but somehow have
forgotten to include an essential part: a function which takes any natural
number and returns the result of applying one step of the above procedure.
Would you be so kind to do that for us?
Input SpecificationThe first line of input consists of a single integer
N, specifying the number of test cases. Then follow N lines,
each containing a single positive integer N to which the above
procedure should be applied. In all cases N will not exceed
Output SpecificationFor each test case you should print one line of
output. If the input equals one, print '
No next number.'. In all
other cases print '
After P we get Q.', where
P is the input number and Q is the result of dividing by 2 or
multiplying by 3 plus 1.
After 1000 we get 500.
After 301 we get 904.
After 17 we get 52.
After 10 we get 5.
No next number.