4073 (PROBTNPO) - The 3n plus One Problem
Find the maximum Collatz Conjecture chain lengths between two given numbers.
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.
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.
- 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.
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.
1 10 100 200 201 210 900 1000 1000 900 900000 1000000
1 10 20 100 200 125 201 210 89 900 1000 174 1000 900 174 900000 1000000 507