Solving Project Euler problem #48 in Scala

Question

I'm trying to learn some Scala and decided to try to tackle some Project Euler problems.

For problem #48, coming from a Python background, my solution is the following one-liner:

print ( (1 to 1000).map(i => BigInt(i).pow(i)).sum % BigInt(10).pow(10) )

Is this idiomatic? Is there a simpler/more readable solution?

Answer 1

Your solution is clean but doesn't scale well. A well known optimization for a^k mod m is to perform all computations modulus m. If m is sufficiently small, we furthermore can switch to native types (this is not the case here !).

val n = 1000
val m = BigInt(10).pow(10)
(for (i <- 1 to n) yield BigInt(i).modPow(i,m)).sum % m

Rounded avarage timing results (Scala 2.9.1 with -optimize) :

n                     1000     | 10000
Initial solution       4.8 ms  |  6700 ms
Fold left              4.8 ms  |  6700 ms
My humble version      0.5 ms  |     5 ms

Answer 2

Your solution is totally valid. Instead of xs.map(f).sum it is possible to use xs.foldLeft(init)(f):

(1 to 1000).foldLeft(BigInt(0)) {
  (sum, n) => sum+BigInt(n).pow(n)
}
// or with /: synonym for foldLeft
(BigInt(0) /: (1 to 1000)) {
  (sum, n) => sum+BigInt(n).pow(n)
}