Problem The 3n + 1

Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1.Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:

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

It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.
For an 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 i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

Output

For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int count_cycle_lenght( int );
int max_cycle_lenght_between(int,int);

int main(){
  int n1;
  int n2;
  while ( (scanf ("%d%d",&n1,&n2))  != EOF){
      int max_cycle = max_cycle_lenght_between(n1,n2);
      printf ("%d %d %d\n",n1,n2,max_cycle);
  }
  return 0;
}

int max_cycle_lenght_between(int n1,int n2){
  int a = min (n1,n2);
  int b = max (n1,n2);
  int max_cycle = 0;

  for ( int i = a; i <= b; i++){
      int result = count_cycle_lenght(i);
      max_cycle = max(result,max_cycle);
  }
  return max_cycle;
}

int  count_cycle_lenght( int n1){
  int count_cycle = 0;
  while (n1 != 1 ){
      if ( (n1 % 2)  == 0){
          n1 /= 2;
      }else{
          n1 *=3;
          n1++;
      }
      count_cycle++;
  }
  count_cycle++; 
  return count_cycle;
}