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 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:
Post a Comment