Program to print the Collatz sequence in javascript.

An algorithm 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.

Leave a Reply

Your email address will not be published. Required fields are marked *