SPOJ PROBTNPO

From Algorithmist
Jump to navigation Jump to search

4073 (PROBTNPO) - The 3n plus One Problem[edit]

Summary[edit]

Find the maximum Collatz Conjecture[1] chain lengths between two given numbers.

Explanation[edit]

Take any natural number, if it is even divide it by two and if it is odd multiply it by three and add one. The Collatz Conjecture states that this sequence will always converge to 1. The object of this problem is to determine the maximum number of iterations to reach 1 for every number between and including the input numbers.

Implementation[edit]

Although this is a classic recursion problem, simple iteration is good enough in this case. Iterate from the first input to the second, passing the loop variable to a function that returns the number of iterations required for that input to converge to 1. Keep track of the maximum value returned from the function.

Gotchas[edit]

  • The intermediate results can climb to very large values before converging to 1. An unsigned long type is suggested for most C/C++ implementations.
  • The input values are not necessarily given in order, so swap them if needed, but be sure to output them in the order given.
  • if you are memoizing, watch your array indices. Just because your input values are constrained doesn't mean the intermediate results are.

Optimizations[edit]

This problem lends itself very well to memoization. The idea of memoization is to save your calculated results for use in future calculations. In this problem it is very easy to check an array index to see if a result for a particular number has already been calculated. If it has, just retrieve it and add the number of iterations up to that point. If it hasn't, store the ultimate result in the array.

Input[edit]

1 10
100 200
201 210
900 1000
1000 900
900000 1000000

Output[edit]

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