Problem: Euler Task 14: Which starting number, under one million, produces the longest chain?

I pick this problem 14 because it provides an interesting example of tuple used in combination with fold. Let's see how it works nicely.

First, the 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?"

Now, we're able to attack the problem. We will need a function that receives a term and returns the length of the chain. Let's say def chainLength(n : Int) : Int . Unfortunately, this will not work out since the term can be bigger than Integer.MAX_VALUE, which is the case when I first tested the problem. So, we'll need instead chainLength(n : Long).  We're ready for the code then.  We have basically four cases, when n <=0, n == 1,  n is odd, n is even. We'll have then something like :

def chainLength(n :Long): Int = {
   if (n <= 0) {
       throw new IllegalArgumentException("Negative term: " + n)
   } else if ( n == 1 ){
      1
   } else if (n% 2 == 0) {
      1 + chainLength(n/2)        
   } else {
     1 + chainLength(n *3  + 1)
   }
}

Almost OK. But the recursion is not tail recursion. We need to make it tail recursive by introducing an accumulator as the second parameter.

def chainLength(n :Long, len: Int): Int = {
   if (n <= 0) {
       throw new IllegalArgumentException("Negative term: " + n)
   } else if ( n == 1 ){
      len
   } else if (n% 2 == 0) {
           chainLength( n/2, len + 1)        
   } else {
           chainLength( n *3  + 1, len + 1)
   }
}

To get the chainLength for 13 we call then chainLength(13, 1)

Great. The only thing missing is now to find the lowest starting term between 2 to 1000000.
Here we're going to use combination of tuple (a, b) where a is the term and b is the length of sequence for the term. Here is the final code:

(2 to 1000000).foldLeft( (2,0) )( (x,y) => {
    val len = chainLength(y, 1)
    if (len > x._2 ) (y, len)
    else x
  })

The code took me less than 6 seconds in my machine.