Euler Problem 14 – Longest Collatz sequence

Longest Collatz sequence

Problem 14

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.

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s