31 Jan 2009

Project Euler problem 21 using Scala

Randomly picking another Euler challenge using Scala, I turned my attention to problem 21 this time. This asks to find the set of Amicable numbers under 10000 and sum them up.
This led to playing around with Scala's Sequence comprehension's a bit. Here's my solution:



object Euler21 {
def sumOfDivisors(number: Int): Int = {
List.range(1, number).filter{i => (number % i) == 0}.foldLeft(0){(a,b) => a+b}
}

def main(args: Array[String]): Unit = {
(for (i <- 0 until 10000; d_i = sumOfDivisors(i);
if(d_i > i && sumOfDivisors(d_i) == i))
yield (i + d_i)).foldLeft(0){(a,b) => a+b};
}
}



I like the brevity of this solution. The function sumOfDivisors first filters out all divisors of a given number and sums the resulting list using the foldLeft function. The main function first computes this sum for each number in the range 1 till 10000. The resulting number, d_i is used for further processing only if it's larger than the original number, this is to avoid double results of the same pair of amicable numbers twice (i.e if we have processed the number 220 and found 284 as its amicable pair, we don't have to go through the same exercise again if we process 284 next in our list). If this holds, we calculate the sum of divisors of the number d_i. If that's equal to our original number, we have a match, so we add the sum of the two numbers it to our output. The output is Scala's Projection trait, so we can obtain the desired sum by adding up all numbers using a foldLeft function again. Incidentally, you may want to check whether the generated sequence of numbers is actually correct. In this case, instead of doing the summing, use this line of code:


for (i <- 0 until 100000; di = sumOfDivisors(i); if(di > i && sumOfDivisors(di) == i) ) yield (Pair(i, di));


When executed this yields the following output:


scala> for (i <- 0 until 10000; di = sumOfDivisors(i); if(di > i && sumOfDivisors(di) == i) ) yield (Pair(i, di));
res2: Seq.Projection[(Int, Int)] = RangeMFM((220,284), (1184,1210), (2620,2924), (5020,5564), (6232,6368))

No comments:

Post a Comment