Program to print the Collatz sequence in javascript.

We will implement different algorithms to print the Collatz sequence in javascript. Everything will be written in ES6.

A Collatz sequence is obtained by performing the following operations on any given number.

• If the number is even then number = number / 2.
• If the number is odd then number = 3 * number + 1.
• Repeat this steps until the number becomes 1.

n = 6
6, 3, 10, 5, 16, 8, 4, 2, 1

A brute-force method.

Implementation

• We will loop till the given number is equal to 1.
• If the number is even then we will do number = number / 2 and print it.
• Else If the number is odd then we will do number = 3 * number + 1 and print it.

let collatz = (num) => {
    // loop till the given num is not 1
    while(num != 1){

      //print the num
      console.log(num);

      //if the number is even
      if(num % 2 == 0){

        num = parseInt(num / 2); 

      }else{
        //if the number is odd
        num = (num * 3) + 1;
      }
    }

  // print the last number
  console.log(num);
}

Input:
collatz(5);
collatz(11);

Output:
5
16
8
4
2
1

11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Time complexity: NA.

Space complexity: O(1).

Time and Space complexity

• There is no specific time for this algorithm as it will till the given number is not 1, so Time complexity is NA.
• We are using constant space, so Space complexity is O(1).

---

With Recursion.

Implementation

• We are going to use an array to store the collatz sequence.
• We will create a function which will call itself recursively if the given number is not 1.
• If the number is even then we will call the same function with number = number / 2.
• Else if the number is odd then we will call it with number = number * 3 + 1.
• If the number is 1 then we will return 1.

let collatzTail = (num, store) => {
    //if num is 1 then store 1
    if(num === 1) { 
        store.push(1);
        return store;

    //if num is even then store num / 2
    } else if(num % 2 === 0) {
        store.push(num); 
        return collatzTail(parseInt(num / 2), store);
      //if num is odd then store num * 3 + 1

    } else {
        store.push(num); 
        return collatzTail(3 * num + 1, store);
    }
};

Input:
let store = [];
collatzTail(6, store);
console.log(store);

let store = [];
collatzTail(10, store);
console.log(store);

Output:
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[10, 5, 16, 8, 4, 2, 1]

If you want you can print this array.

Time complexity: NA.

Space complexity: NA.

Time and Space complexity

• There is no specific time to this algorithm because it is condition based, so Time complexity is NA.
• As this is running on condition there can be any number of call stack, so Space complexity is NA.