Wednesday, November 3, 2010

Problem: Euler Task 12: Number of factors of triangle number.

The following problem (euler 12) is a good example of the use of Stream collection in Scala. The use of Stream is explained in http://www.scala-lang.org/docu/files/collections-api/collections_14.html .
Basically, using Stream, we can create a list that computes its elements lazily. For example, to create a list of fibonacci number we can use 

def fibFrom(a: Int, b: Int): Stream[Int] = 
             a #:: fibFrom(b, a + b)



"The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?"

The triangle number here is a good candidate for Stream collection.  We can define the triangle function as follow:

 1 def triangle(a: Int, b: Int) : Stream[Int] = 
 2    a #:: triangle(a + b + 1, b + 1)



Which means the first element of triangle number list is a and the next element is (a + b + 1), followed by ( a + b + 1 + b + 1 + 1), and so on .
triangle(1, 1).take(7).foreach(println) prints the first 7 triangle numbers.

The following function computes the number of factors of an integer:

1 def nfactor(n: Int): Int = 
2        (1 to csqrt(n)).foldLeft(0)( 
3         _ + incrfactor(n, _))


where incrfactor is a function that receives two parameters (n, x) and returns 0 if x does not divide n, 2 if x divides n and n/x != x , 1 otherwise (because when n/x = x ,we have only found one factor = x , otherwise if we have found 2: x and n/x).

1 def incrfactor(n: Int, x: Int) =
2     if (n % x == 0) (
3        if (x == n/x) 1 else 2
4     ) else 0    


With all these on our hands, we're ready to answer the problem. The answer to our problem is

triangle(1,1).find( nfactor(_) > 500)

which returns the first triangle number that has more than 500 factors. In my computer, the code above needs 6 s.

No comments: