// 
// The 3n+1 Problem (Programming Challenges) in SetlX
// 
// Skiena: Programming Challenges, page 15.
// """
// 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.
// Sample Input Sample Output
//    1 10         1 10 20
//    100 200      100 200 125
//    201 210      201 210 89
//    900 1000     900 1000 174
// """
// 
// Note: This sequence is also called Collatz sequence and Hailstone sequence.
// There are some other programs regarding this:
//   hailstone_sequence.stlx
//   euler14.stlx
// 
// This SetlX program was created by Hakan Kjellerstrand (hakank@bonetmail.com)
// Also see my SETL page: http://www.hakank.org/setl/
//

// Using built-in cache
collatzLen := cachedProcedure (n) {
  if (n <= 1) { return 1; }
  if (n % 2 == 0) {
    return collatzLen(n \ 2) + 1;
  } else {
    return collatzLen(3*n + 1) + 1;
  }
};

collatzSeq := cachedProcedure (n) {
  if (n <= 1) { return [1]; }
  if (n % 2 == 0) {
    return [collatzSeq(n \ 2) + 1, n];
  } else {
    return [collatzSeq(3*n + 1) + 1, n];
  }
};

collatz := cachedProcedure(n) {
  if (n <= 1) { return 1; }
  if (n % 2 == 0) {
    return n \ 2;
  } else {
    return 3*n + 1;
  }
};


input :=
"1 10
100 200
201 210
900 1000
1 10000
1 100000
1 1000000
800000 900000";

s := [[int(j) : j in split(i, "\\s")] : i in split(input, "\n")];

for ([i,j] in s) {
  t1 := now();
  print("$i$ $j$ $max([ collatzLen(n) : n in [i..j]])$");
}
