Maximum Collatz sequence under 1000000

We will implement an optimized algorithm to print the number with the maximum count of numbers in a Collatz sequence under 1000000 in javascript. Everything will be written in ES6.

Learn more about Collatz sequence.

Implementation

• We will use dynamic programming to solve this.
• We will use a object to store the count of already computed collatz sequence.
• Then loop through all the numbers upto 1000000 and find the collatz sequence of each of them if it is not already computed and store it.

let collatzSequence = () => {
 
    let memo = {}; //Store already computed sequence count
    let max = 0;   //Store the max count
    let index = 0; //Store the number with max count
   
    //loop from 1 to 1000000		
    for(let j = 1; j <= 1000000; j++){
        
	let count = 1; //initialize the count
	let i = j;     // use temp variable to compute the collatz sequence
        
        // compute the collatz sequence
	while(i > 1){
    
         //if the sequence is not already present then compute it
	 if(!memo[i]){
	    i = (i % 2 == 0) ? parseInt(i / 2) : parseInt((3 * i) + 1);
	    count++;
	 }else{
            //Else update the count with already stored sequence count
            count = count + memo[i] - 1;			
	    break;
	 }
       }
   
        //store the sequence for the given number
	memo[j] = count;
        
        //get the max count and number with max count
	if(max < count){
	  max = count;
	  index = j;
	}
    }
  
  //return the number
  return index;
}

Input:
console.log(collatzSequence());

Output:
837799

Time complexity: NA.

Space complexity: O(1).

Time and Space complexity

• We are iteating from 1 to 1000000 but there is no specific time of computing the collatz sequence of each numbers, so Time complexity is NA.
• We are using constant space of 1000000 to store the sequence count, so Space complexity is O(1).