Programming Problem #23
"3N+1"

Consider the following program. Assume that the input N is a positive integer.
  1. input N
  2. print N
  3. if N=1 then stop
  4. if N is odd then N := 3N+1 else N := N/2
  5. goto 2
This program will print a sequence of integers. For example, if N is initially 22 it will print the sequence 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

It is conjectured that this sequence if finite for all N; in other words, the program will eventually stop no matter what the initial value of N. This has been verified for all values of N at least through one billion, but no general proof of termination has been found.

For any N, the length of the sequence printed by the program is called the cycle-length of N. For example, the cycle-length of 22 is 16. Your job is to write a program to compute the maximum cycle-length of any number within a specified range.

The input consists of one or more pairs (A,B) of nonnegative integers. Each pair of numbers is separated by a space and is on a line by itself. If A=0 it signals the end of the input. Otherwise, A will be less than or equal to B, and B will be at most 10,000. For each such pair your program must output the maximum cycle-length of any number between A and B, inclusive. Note that a brute-force approach will take too much time.

Input must be read from the file "prob23.in", and output must be written to the file "prob23.out". All output to the screen will be ignored.

Example Input

<BOF>
100 200
900 1000
1 10
201 210
0 0
<EOF>

Example Output

125
174
20
89
A version of this problem (originally?) appeared in the 1990 Duke Internet contest.

Dr. Eric Shade