Unveiling the Fascination of the Collatz Conjecture: Exploring Sequence Creation with JavaScript

The Collatz Conjecture, also known as the 3x+1 problem, is a fascinating mathematical puzzle that has intrigued mathematicians for decades. It has sparked publications with titles such as The Simplest Math Problem Could Be Unsolvable, or The Simple Math Problem We Still Can’t Solve because it is, indeed, rather simple-looking.

It proposes a simple rule to generate sequences of numbers, yet its behavior – and the ability to prove it – remains elusive. These problems in mathematics are always quite fascinating; if you enjoy them, you might also like a book by Simon Singh titled Fermat’s Enigma: The Epic Quest to Solve the World’s Greatest Mathematical Problem. We hope you enjoy this article; if you do, please consider sharing it.

Let’s delve into the Collatz Conjecture. We’ll also be writing two algorithms to generate Collatz sequences.

Understanding the Collatz Conjecture

There’s not much to the Collatz conjecture. It defined as follows: Start with any positive integer n. If n is even, divide it by 2; if n is odd, multiply it by 3 and add 1. Repeat this process with the resulting number.

The conjecture posits that no matter which positive integer n you start with, the sequence of numbers generated will always eventually reach the value 1, and then enter an endless loop of 4, 2, 1.

For the nerds (probably everyone reading this article, including myself), the mathematical function for this looks like this:

After looking at that, you might have already thought of a way to translate that into code. If not, no worries, we’ll be covering that down below.

If we start with n = 12, we know that n is an even number, so we divide the number by 2, getting 6, which is also even. Dividing 6, we get 3, our first odd number, so we enter the second condition 3 x 3 + 1, getting 10, and so on.

The entire sequence for f(12) is 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

Incredibly simple, no? Although it’s extremely simple, it’s worth mentioning again that this conjecture remains unproven. Perhaps someone reading this article will decide to tackle it. (If you manage to solve it, please let us know. 😁)

Generating a Sequence with JavaScript

As we mentioned earlier, after looking at the mathematical function above, you might have thought of the first solution (or perhaps you’ve come up with something more clever) we’re about to explore. If you haven’t, please do feel free to try implementing an algorithm that produces the appropriate sequence. Indeed, all of the information you need is above.

However, here’s some pseudocode to get you started:

Start with the number n and create an empty sequence to store the numbers.
Add n to the sequence.
While n is not equal to 1:
    If n is even, divide it by 2.
    If n is odd, multiply it by 3 and add 1.
    Add the new value of n to the sequence.
Once n becomes 1, the sequence is complete.
Return the sequence.

Give it a try before scrolling down to the solutions!

Random picture of a cat to give you one last chance to attempt the problem.

That’s a cute kitty, eh?

. . .

Okay, okay, enough of that. Let’s get to it then.

Solution 1:

The first solution we offer is usually the simplest. That’s true for this case too. Let’s take a look.

function collatzSequence(n) {
  let sequence = [n];

  while (n !== 1) {
    if (n % 2 === 0) {
      n /= 2;
    } else {
      n = n * 3 + 1;
    }

    sequence.push(n);
  }

  return sequence;
}

console.log(collatzSequence(12)); // 12, 6, 3, 10, 5, 16, 8, 4, 2, 1

Now, if you went to the GitHub repository above, you’ll notice this solution is lacking some logic – it doesn’t handle 0, 1, or undefined as inputs. This is to simplify things for the sake of the article, so do keep that in mind.

However, this solution is rather quite simple, no? The most common misstep would probably be forgetting to include the initial value of n within the array, sequence. So if you were wondering why the tests weren’t passing as you worked your way through the challenge, there’s a good chance that’s what you missed.

Other than that, the code reads pretty much like English. While n is not equal to 1, check if it’s even, dividing it by 2, else it’s odd, set n equal to n times 3 plus 1.

Solution 2:

It makes sense to try to optimize the algorithm. But how exactly can we do that?

Well, we can employ a concept known as memoization, which essentailly caches previously calculated values. This means that if the sequence for a given input has already been calculated, it will be retrieved from the cache rather than recalculating it altogether.

Let’s see how this is done.

const memo = {};

function collatzMemoized(n) {
    if (memo[n]) return memo[n];
    if (n === 1) return [1];

    let sequence = [n];

    if (n % 2 === 0) {
        sequence = sequence.concat(collatzMemoized(n / 2));
    } else {
        sequence = sequence.concat(collatzMemoized(3 * n + 1));
    }

    memo[n] = sequence;
    return sequence;
}

console.log(collatzMemoized(12));

First up, we have an empty object being assigned to memo. As you might have guessed, this object is going to be used to store previously calculated sequences to avoid redundant calculations. The next important piece of code in the above block is if (memo[n]) return memo[n];, which checks to see whether or not the collatz sequence for a given number n has already been calculated and stored within the memo object. If it has, the function returns the cached sequence, avoiding extra calculations.

In this solution, we also need a base case, as we’re calling the function recursively. That’s precisely why we’re checking if (n === 1). If n is indeed equal to 1, return an array containing only the number 1.

The next interesting bit is checking if a number is even. If it is, sequence is going to be set to sequence.concat(collatzMemoized(n / 2)), our first taste of recursion, which essentially calls the function again if the value is even. Likewise, if the value is false, the code calls the function yet again with the new value.

After calculating the Collatz sequence for the current number n, the resulting sequence is stored in the memo object with n as the key. This allows the function to reuse the sequence for future calculations.

The final part of the function simply returns the sequence.

Conclusion

This was one of our favorite challenges. Mathematicians still can’t provie it, and it’s extremely simple. Simple enough for a young child to understand.

We sincerely hope you found this article enjoyable. Consider leaving a comment or reaction down below and don’t forget to check out the GitHub repository.

Happy Hacking!