# 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](https://en.wikipedia.org/wiki/Collatz_conjecture#:~:text=The%20Collatz%20conjecture%20is%20one,every%20positive%20integer%20into%201.), 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`.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1673430661937/81f7077a-4140-482a-9027-1d3f0792b471.png align="center")

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**

```javascript
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,

```javascript
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](https://github.com/sansk/project-euler-solutions-javascript/tree/main/14)

For [**Hackerrank**](https://www.hackerrank.com/contests/projecteuler/challenges/euler014/problem), 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](https://github.com/sansk/project-euler-solutions-javascript/blob/main/14/HackerrankSolution.js). 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.**](https://theintrovertcoder.hashnode.dev/series/project-euler)

Thank you!