**Longest Collatz sequence**

**Problem 14**

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

*n* → *n*/2 (*n* is even)

*n* → 3*n* + 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.

This was one challenging question. Finding a number under one million producing the longest Collatz sequence, sounds computationally expensive? My approach was to first get to the solution and then think how to optimize it. Reaching to the solution is more important than optimizing it.

I wrote a separate function which would take a number as input and generate a collatz sequence of that number. I have a written a recursive function named ` generateCollatzSequence`

which would return if the number is 1, if the number is even it would divide it by half (n/2) and if the number is odd it would make it to 3*num + 1.

generateCollatzSequence = function(vec, num) { vec = append(vec, num) if(num == 1) { return(vec) } if(num %% 2 == 0) num = num / 2 else num = 3*num + 1 generateCollatzSequence(vec, num) }

So when we run

` generateCollatzSequence(13) `

it returns

` [1] 13 40 20 10 5 16 8 4 2 1 `

The main function is `get_highest_CNumber`

which accepts a number (here 1, 000, 000) and for every number from 1 to that number, it generates a collatz sequence and selects the one which is the biggest.

Source(“14. GenColSeq.R") get_highest_CNumber = function(num) { highestSeq = 0 for(i in seq(num)) { vec = numeric() newvec = generateCollatzSequence(vec, i) if(length(newvec) > highestSeq) { highestSeq = length(newvec) highestSeqNumber = i } } return(highestSeqNumber) } get_highest_CNumber(1000000) #[1] 837799

and the length of the Collatz sequence of this number is 525.