The following iterative sequence is defined for the set of positive integers:
n → 3n + 1 (n is odd)
Which starting number, under one million, produces the longest chain?
The Naive Approach
The first thought I had when I read this problem was "This is easy." Of course, I could easily use the brute force solution:
const limit = 1000000;
let maxChain = 0;
let answer;
function Collatz(num) {
let count = 0;
while(num != 1) {
if (num % 2 === 0) {
num /= 2;
count += 1;
} else {
num = 3 * num + 1;
count += 1;
}
}
count += 1;
return count;
}
for (let i = 1; i < limit; i++) {
const chain = Collatz(i);
if (chain > maxChain) {
maxChain = chain;
answer = i;
}
}
console.log(answer);The second thought I had was: "It can't possibly be this easy..."
The more I stared at the question, the more opportunities I found for optimization.
The Actual Approach
Optimization #1: Constraining the Bounds
Let's look at line #20 in the naive approach. Do we really need to search through almost 1 million positive integers to find our solution? The Collatz Conjecture states that the Collatz sequence for any positive integer $x$, after some number of steps, will eventually reach $1$. In other words:
$$x\to \cdots \to 1$$Consider for a moment the Collatz sequence for the positive integer $2x$. We know for a fact that $2x$ must, by definition, be even. After all, it can be evenly divided by 2. From the question, we know that the handling of an even number is $n\to n/2$. Since we are assuming $n = 2x$, the Collatz sequence for $2x$ looks like this:
$$2x\to x\to \cdots \to 1$$We can infer from this thought experiment that $\text{Collatz}(2x) = \text{Collatz}(x) + 1$, which means that $\text{Collatz}(2x) > \text{Collatz}(x)$ regardless of the value of $x$.
How does this fact help us? Look again at line #1 of the naive approach. If we assume that our answer is under our limit variable, than the lowest value that our solution could possibly be is limit / 2, since any value under that has a corresponding $2x$ above limit / 2.
Here is an example: For this problem, $\text{limit} = 1000000$ and $\text{limit}/2 = 500000$. That means that $\text{Collatz}(300000)$ could not possibly be the answer, because $\text{Collatz}(600000)$ is sure to be greater. It makes no sense for us to bother trying to calculate any number below $\text{limit}/2$.
We can then change line #20 of the Naive Approach to the following:
for (let i = Math.floor(limit / 2); i < limit; i++) {Optimization #2: Double-stepping during Odd Number Handling
Let's look back at lines #12 & #13 in the naive approach. The problem states that if $n$ is odd, $n\to 3n+1$. It's interesting to note that, within the context of $n$ being odd, $3n+1$ will always yield an even number. To prove this, let's think about a hypothetical number $e$ which represents any even natural number. This means that $e-1$ represents any odd natural number. Let's now assume that $n=e-1$ and run it through our odd number handling equation.
$$3\times n+1$$ $$3\times (e-1)+1$$ $$3e-2$$ $$e+ e+ e - 2$$We can see that when any odd number is run through the $3n+1$ equation, it reduces to a term for which every component is divisible by 2. Since, in our implementation, only odd numbers are run through $3n+1$ we can assume that it will produce an even number and apply the even number handling equation immediately (thereby saving an iteration). This means we change line #12 and #13 to read:
num = (3 * num + 1) / 2
count += 2;Optimization #3: Re-using Past Work
If you think about the problem just a little bit, a glaring realization will pop up. You will realize that the naive approach is repeating work it has already done. Let's list the Collatz sequences for 4 and 5:
$$4\to 2\to 1$$ $$5\to 16\to 8\to ( 4\to 2\to 1 )$$Once the Collatz sequence for 5 gets to 4, all the naive approach does is repeated. This is happening for almost 1 million integers. We can save all this time if we could store the Collatz chain length for all numbers that we previously calculated and reference it when calculating a new number.
Javascript's array object is a perfect data-structure to use to accomplish this. The index of the array represents the number to be checked and the value stored represents the length of Collatz chain for that index. To help conceptualize what that might look like, here is the contents of the array in question for numbers $1\to 10$.
| Index | Value |
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 8 |
| 4 | 3 |
| 5 | 6 |
| 6 | 9 |
| 7 | 17 |
| 8 | 4 |
| 9 | 20 |
| 10 | 7 |
With each iteration, we can check if we've calculated the length of the Collatz chain of that number before, and if so, we can add that chain to the one we've calculated so far... and we're done! We can move on to the next number.
There is just one caveat. There are some chains that produce numbers in excess of 3 million. An array with that many indexed values may be a bit much for our computer to handle. It would make sense for us to focus on storing the chain lengths of those numbers that are below our limit variable, since those will be referenced most often.
To implement this optimization, we are going to add a variable named _cache in the global scope that we initialize to the value of [0, 1]. The 0th index will never be used, but it's important to include the 1st index by default. The _cache variable can be passed into the function as an arguement by altering line #5 of the Naive Approach like so:
function Collatz(num, cache = _cache) {The while-loop will still terminate once num variable reaches 1 if we alter the beginning of the while-loop to look like this:
while(true) {
if (cache[num]) {
count += cache[num];
break;
}
// ...
}Optimization #4: Deducing Future Work
We saw from the previous section that every Collatz sequence contains a sub-sequence of another number. We saw that it's possible for us to cache the Collatz sequence length in an array. What I will try to suggest in this section is that we should not only cache the Collatz length of the number we are evaluating, but we can cache the Collatz length of all of the other numbers in the sequence in a way that would save many iterations of our while-loop (on line #7 of the Naive approach).
Let's look at some of the sub-sequences in the Collatz sequence for 13:
$$13\to (40\to 20\to 10\to 5\to 16\to 8\to 4\to 2\to 1)$$ $$13\to 40\to (20\to 10\to 5\to 16\to 8\to 4\to 2\to 1)$$ $$13\to 40\to 20\to (10\to 5\to 16\to 8\to 4\to 2\to 1)$$ $$13\to 40\to 20\to 10\to (5\to 16\to 8\to 4\to 2\to 1)$$Notice that the above sequence also contains the sequence for 40. Assuming we are iterating from $1\to \text{limit}$, than when we arrive at 13, we will not yet have evaluated 40. When we actually do get to 40, we will have to evaluate 40 from scratch (assuming we are using the naive approach). This is unnecessary, since we have already processed it. In fact, it can be calculated mathematically. We can see from the above example that $\text{Collatz}(40) = \text{Collatz}(13) - 1$. In fact, every number in the sequence can be calculated this way:
| Sequence | Calculation | Collatz Length |
| 13 | $\text{Collatz}(13)-0$ | 10 |
| 40 | $\text{Collatz}(13)-1$ | 9 |
| 20 | $\text{Collatz}(13)-2$ | 8 |
| 10 | $\text{Collatz}(13)-3$ | 7 |
| 5 | $\text{Collatz}(13)-4$ | 6 |
| 16 | $\text{Collatz}(13)-5$ | 5 |
| 8 | $\text{Collatz}(13)-6$ | 4 |
| 4 | $\text{Collatz}(13)-7$ | 3 |
| 2 | $\text{Collatz}(13)-8$ | 2 |
| 1 | $\text{Collatz}(13)-9$ | 1 |
We can see from the table above, that every number in the sequence can be calculated mathematically. We need only 3 pieces of information:
- The first number in the sub-sequence. So we know which index to cache the sub-sequence length. We can use the
numvariable from within the while-loop to access that information. - The collatz length of the parent sequence. This is calculated and stored in the
countvariable after the while-loop (line #17 in the Naive approach). - The position of the first sub-sequence number in the parent sequence. We can use
countvariable from within the while-loop because it is updated as the while-loop progresses.
It's important for us to restrict which numbers are calculated in this way. Firstly, in the Collatz sequence for 13, the numbers 40 and 20 represent future work but numbers below 16 have already been calculated and cached so we need not repeat that work. Secondly (and most importantly), we must restrict numbers that are so large that they become troublesome to store. Remember from the previous section that we are storing these numbers in an array. Some sequences produce numbers that are in excess of 3 million. Having an array that stores that many items will absolutely cause difficulties. In my solution, I've restricted storage to numbers under our limit variable.
To implement this optimization, we need to add a variable within our Collatz function. We will call it stack and intialize it to an empty array. The stack array will hold all the future work that we will calculate mathematically after the while loop is concluded.
We can now extend the if-statement from the previous section to store the information we need. We can then apply the mathematics once the while loop concludes:
while(true) {
if (cache[num]) {
// ...
} else if (num < limit) {
stack.push({
num,
position: count
})
}
// ...
}
for (let entry of stack) {
let {num, position} = entry;
cache[num] = count - position;
}Putting it all together!
const _cache = [0, 1];
const limit = 1000000;
let maxChain = 0;
let answer;
function Collatz(num, cache = _cache) {
let count = 0;
const stack = [];
while(true) {
if (cache[num]) {
count += cache[num];
break;
} else if (num < limit) {
stack.push({
num,
position: count,
});
}
if (num % 2 === 0) {
num /= 2;
count += 1;
} else {
num = (3 * num + 1) / 2;
count += 2;
}
}
for (let entry of stack) {
const {num, position} = entry;
cache[num] = count - position;
}
return count;
}
for (let i = Math.floor(limit / 2); i < limit; i++) {
const chain = Collatz(i);
if (chain > maxChain) {
maxChain = chain;
answer = i;
}
}
console.log(answer);