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 problem is available here: http://projecteuler.net/index.php?section=problems&id=12 :

"

*The sequence of triangle numbers is generated by adding the natural numbers. So the 7*^{th}*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)else0

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:

Post a Comment