Description

Consider the following algorithm to generate a sequence of numbers. Starting with an integer n:

1. If n is even, then divide by 2.
2. If n is odd, then multiply by 3 and add 1.

Repeat this process for each new value of n until n is 1. For instance if n = 22, then the following sequence would be generated:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It has been conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. It is guaranteed, however, to hold at least up to 1,000,000.

For every input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.

Input

The input will consist of a series of pairs of integers, one pair per line. All integers will be less than 1,000,000 and greater than 0. Here is an sample input:

1 10
100 200
201 210
900 1000

Output

For each pair of input integers, output the pair in the same order that they were read and then the maximum cycle length for the integers between the range specified by the pair. Here is an sample output:

1 10 20
100 200 125
201 210 89
900 1000 174

Approach

Compute all of the cycle lengths for each number in the range, and store the max as you perform this computation. Optionally, store these computations in a table to prevent repeated computations (i.e. dynamic programming).

Input/Output

• Final Input: problem014.input
• Final Output: problem014.output

Source Code

• Peter Bui's source code: pbui.c
• Tommy Walton's source code: twalton1.cpp