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))

37 comments:

  1. Always keep your words soft and sweet, just in case you have to eat them.............................................

    ReplyDelete
  2. 來給你加加油~打打氣!!!更新之餘,也要注意休息哦~~ ..................................................

    ReplyDelete
  3. 卡爾.桑得柏:「除非先有夢,否則一切皆不成。」共勉!............................................................

    ReplyDelete
  4. 在你一無所有的時候 是誰在陪伴你 他便是你最重要的人............................................................

    ReplyDelete
  5. 做好事,不需要給人知道,雖然只是一件微不足道的事,但我相信,這會帶給我快樂。..................................................

    ReplyDelete
  6. A truly happy person is one who can enjoy the scenery on a detour. ............................................................

    ReplyDelete