eolymp
bolt
Try our new interface for solving problems
Problems

The 3n + 1 problem

The 3n + 1 problem

Consider the following algorithm: 1. input \textbf{n} 2. print \textbf{n} 3. if \textbf{n} = \textbf{1} then STOP 4. if \textbf{n} is odd then \textbf{n} = \textbf{3} * \textbf{n} + \textbf{1} 5. else \textbf{n} = \textbf{n} / \textbf{2} 6. GOTO 2 Given the input \textbf{22}, the following sequence of numbers will be printed \textbf{22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1}. It is conjectured that the algorithm above will terminate (when a \textbf{1} is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers \textbf{n} such that \textbf{0} < \textbf{n} < \textbf{1,000,000} (and, in fact, for many more numbers than this.) Given an input \textbf{n}, it is possible to determine the number of numbers printed (including the \textbf{1}). For a given \textbf{n} this is called the cycle-length of \textbf{n}. In the example above, the cycle length of \textbf{22} is \textbf{16}. For any two numbers \textbf{i} and \textbf{j} you are to determine the maximum cycle length over all numbers between \textbf{i} and \textbf{j} inclusive. \InputFile The input will consist of a series of pairs of integers \textbf{i} and \textbf{j}, one pair of integers per line. All integers will be less than \textbf{1,000,000 }and greater than \textbf{0}. You can assume that no operation overflows a \textbf{32}-bit integer. \textbf{ Output} For each pair of integers \textbf{i} and \textbf{j} you should output \textbf{i} and \textbf{j} in the same order in which they appeared in the input. Then print the maximum cycle length for integers between and including \textbf{i} and \textbf{j}. For each test case print three numbers on one line, separating them by one space.
Time limit 1 second
Memory limit 128 MiB
Input example #1
1 10
100 200
201 210
900 1000
Output example #1
1 10 20
100 200 125
201 210 89
900 1000 174