# Hackerrank – Project Euler+ #014 – Longest Collatz sequence

## Hackerrank – Problem description

The problem description – Hackerrank.

## Solution

There are given 2 rules for Collatz sequence:

• if `n` is even, then `n/2`
• if `n` is odd, then `3n + 1`

The given problem set of possibilities is to big and it would take too much time.

My solution is to precalculate sequence values of `1` to `5 000 000` and then to store them into a cache to reuse them.

For `1` there is a size of Collatz sequence `1` unit.

`2`: I use the rule and divide it by `2`, because it is even. The sequence would by `2` long – The result of division is `1`. I look into the cache and I see that I have calculated the size of the sequence with starting value as `1` is `1`.

`3` similar: There is nothing in the cache for `3`. I need to multiply and increment `1`. The result is `10` (actual sequence size is `1`). `10` is not in the cache, I need to divide. The result is `5` (the sequence size is already `2`). `5` is not in the cache, I need to multiply and the result is `16` (the sequence size is `3`). `16` is not in the cache and I need to divide by `2` with the result `8` (size of the sequence is `4`). `8` is not in the cache, I need to divide with the result `4` (size is `5`). `4` is not in the cache, divide by `2`, result is `2` (size is `6`). `2` is present in the cache and its size is `2`. I sum the sizes `6 + 2`.
It means that the size of Collatz sequence for the number `3` `is 8`.

`4`: It is not in the cache, divide by `2` with the result `2` (actual size of the sequence is `1`). `2` is in the cache with the length value `2`. The complete size of the Collatz sequence is `1 + 2 = 3`.

etc.

I need to remember the longest Collatz sequence:

• `1`: from `1` to `1` is the longest sequence `1` unit
• `2`: from `1` to `2` is the longest sequence `2` (`1` has the sequence `1` unit long)
• `3`: from `1` to `3` is the longest sequence `8`
• `4`: from `1` to `4` is the longest sequence `8` (`1` has `1`, `2` has `2`, `3` has `8` and `4` has `3`)

I created solution in:

All solutions are also available on my GitHub profile.