Project Euler: #14 - Longest Collatz sequence

Problem

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Problem Description

According to Wikipedia, the Collatz conjecture or Collatz problem is,

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1.

Depending on whether n is odd or even, we perform either one of the operations until we reach 1.

Example sequence of 13 is 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 and it contains 10 terms

We need to find the number with the longest sequence under 1000000

Approach

We can approach this in two steps.

First, for each n, we apply the above formula until we reach 1 and count the number of times we have applied the formula. This gives the length of the chain for n.

Then we compare it with the longest sequence so far until we reach the limit of one million. This way we can return the number with the longest sequence under one million.

Another smart way is to cache all the sequence lengths along the way. Look up the cache for the sequence length of n and if found, then return the length or else continue with the calculation.

Note: Please note that the solution provided is only for learning purposes. Once you understand the problem, please try it on your own before referring to my solution below.

Solution

const collatzSeqCount = n => {
    let seqCount = 1;

    if (n === 1) seqCount = 1;

    while (n > 1) {
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            // You can skip to next possible odd using (3n + 1)/2 while adding 2 to the counter 
            // as (3n + 1) always results in even which again is divided by 2 in the next step.
            // Check HackerreankSolution.js for that approach.
            n = (3 * n + 1);
        }
        seqCount++;
    }
    return seqCount;
}

const calcLongestSeq = limit => {
    let longestSeq = 1,
        longestVal = 1;

    for (let i = 2; i <= limit; i++) {
        let getSeqArrCount = collatzSeqCount(i);

        if (getSeqArrCount >= longestSeq) {
            longestSeq = getSeqArrCount;
            longestVal = i;
        }
    }
    return longestVal;

}

console.log(calcLongestSeq(1000000));

Using the caching technique, the collatzSeqCount method can be rewritten as,

let seqCountMap = new Map();
const collatzSeqCountAnoterMethod = n => {
    let seqCount = 1,
        initial = n;

    if (n === 1) {
        seqCount = 1;
    }

    while (n > 1) {
        if (seqCountMap.has(n)) {
            seqCount += seqCountMap.get(n);
            return seqCount;
        }

        if (n % 2 === 0) {
            n = n / 2;
        } else {
            n = (3 * n + 1);
        }
        seqCount++;
    }
    seqCountMap.set(initial, seqCount);
    return seqCount;
}

Used Javascript Map() object for caching the calculated sequence length. This function can be further optimised.

You can find my solution on GitHub 14

For Hackerrank, modified the solution a bit as we know the upper bound of all the test cases to be 5 million. HR solution can be found in this repo. As said before, the code can be further optimised.

If you have any feedback, please leave it below.

If you have any suggestions to improve my code or another way to approach this problem, leave it in the comment.

For the other Project Euler Solutions, please follow the series Project Euler Solutions in JS.

Thank you!

Project Euler: #14 - Longest Collatz sequence

Comments

Project Euler: JS Solution Explained!

Project Euler: #15 - Lattice paths

More from this blog

What is JavaScript and How It Powers Modern Websites

Project Euler: #17 - Number letter counts

Project Euler: #16 - Power digit sum

Project Euler: #15 - Lattice paths

Problem

Problem Description

Approach

Solution

Command Palette

Comments

Project Euler: JS Solution Explained!

Project Euler: #15 - Lattice paths

More from this blog

Problem

Problem Description

Approach

Solution