|
CollatzProjectWiki
Introduction Given two positive integers specifying an inclusive range, this program computes the maximum cycle length of integers within that range. For example, given integers i and j, the range specified is [min(i,j) max(i,j)]. The Collatz cycle begins with a positive integer x and begins recursively mapping the previous integer (call it n) in the cycle to: 3n+1 if n odd, and n/2 if n even. Given any positive integer x below 1,000,000, the cycle has been shown to terminate at 1 after finitely many steps. We call the number of steps it takes to terminate the Collatz cycle beginning at a number x the "Collatz cycle length of x." Note: this function can compute the cycle length of any number whose cycle contains integers capable of being stored in a Java int (32-bit). In this particular case, the range of suitable integers is [1,113382]. Basic approach The algorithm essentially loops through each number within the range and computes that number's Collatz cycle length. If that cycle length is larger than the maximum cycle length seen previously in the loop, the output variable (storing the total maximum cycle length) is updated to reflect this new number. To compute the Collatz cycle length for a given number x, the algorithm starts with x, computes the next number in the cycle (as stated in the Introduction), and iterates the cycle length counter by 1. Details Three major optimizations have been made to the somewhat naive approach outlined above:
|