# 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!

💡 We’ve set up a GitHub repository for challenges like this. This `collatz`

challenge will be the first one in the repository. These challenges will be complete with tests, so feel free to star the GitHub Repository, and give it a try by cloning the project on your machine. Instructions to run the tests are contained in the README of the repository.

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!

## Related Posts

### Solving a Common Interview Question: the Two Sum Algorithm in JavaScript

Imagine you’re at a lively party, and everyone is carrying a specific number on their back. The host announces a game – find two people whose numbers add up to the magic number, and you win a prize!

Read more### Remove Duplicates from Arrays and Strings in JavaScript

Removing duplicates is a common problem in programming that can arise in various contexts, such as cleaning up data or ensuring unique entries.

Read more### Remote First: 5 Websites for Remote Job Opportunities

Would you prefer to work in an office, or while sitting at a beach somewhere in Thailand (i.e. remotely)? Okay, maybe there’s no beach in this scenario, but there’s definitely silence, and maybe your cat.

Read more