Scala for Project Euler

Scala logo, e^ipi + 1 = 0Project Euler is a collection of interesting computational problems intended to be solved with computer programs. Most of the problems challenge your skills in algorithm design rather than your knowledge of mathematics.

Thanks to short concrete problems and number-only solutions you don’t have to thinker with IDEs, GUI designers, programming libraries and frameworks, so Project Euler is an excellent tool for learning a new programming language or improving your core programming skills.

Why use Scala

Although all general-purpose programming languages are Turing-complete and thus suitable for Project Euler, each language has its own philosophy and set of tools. In spite of programming language “holy wars”, the truth is that different tasks demand different tools.

Since Scala is a multi-paradigm programming language, it allows programmers to efficiently express a wide range of common programming patterns. Most Project Euler problems imply advanced transformation of numeric or symbolic data and Scala’s functional programming features are the perfect tool for that purpose (moreover, unlike pure functional languages, being a hybrid language, Scala provides object-oriented capabilities when modeling or simulation is required).

So, what does Scala have to offer for Project Euler? Here is the list of most valuable features:

  • scripting,
  • type-inference,
  • first-class functions,
  • tail call optimization,
  • lazy evaluation,
  • excellent collection library,
  • sequence comprehensions.

On the top of everything else, Scala brings enjoyment to your coding. According to The Right Tool Scala is ranked high in the following categories:

Thus Scala is the right tool for those who want to mingle the useful with the pleasant.

Sample solutions

This section contains solutions to the first 33 problems. You may use them either to size up how well Scala plays in Project Euler, or to compare your own solutions with the samples.

Keep in mind, that the purpose of these solutions is to demonstrate Scala in the first place, so the problems are just a “canvas” to show the elegance and expressiveness of the language. Many times I intentionally preferred a direct and concise solution (if it performs reasonably fast) to a “math-savvy” one.

All the code is available as a GitHub repository.

See also: Ninety-Nine Problems in Scala, Java, Clojure and Haskell.
 

Problem 1
Add all the natural numbers below one thousand that are multiples of 3 or 5.*
val r = (1 until 1000).view.filter(n => n % 3 == 0 || n % 5 == 0).sum

assert(r == 233168) // 7 ms
Problem 2
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.*
lazy val fs: Stream[Int] = 
  0 #:: 1 #:: fs.zip(fs.tail).map(p => p._1 + p._2)

val r = fs.view.takeWhile(_ <= 4000000).filter(_ % 2 == 0).sum

assert(r == 4613732) // 1 ms
Problem 3
Find the largest prime factor of a composite number.*
def factors(n: Long): List[Long] =
  (2 to math.sqrt(n).toInt).find(n % _ == 0)
    .map(i => i.toLong :: factors(n / i)).getOrElse(List(n))

val r = factors(600851475143L).last

assert(r == 6857) // 1 ms
Problem 4
Find the largest palindrome made from the product of two 3-digit numbers.*
val r = (100 to 999).view
        .flatMap(i => (i to 999).map(i *))
        .filter(n => n.toString == n.toString.reverse)
        .max

assert(r == 906609) // 102 ms
Problem 5
What is the smallest number divisible by each of the numbers 1 to 20?*
val r = Range(20, Int.MaxValue)
        .find(n => Range(2, 21).forall(n % _ == 0)).get

assert(r == 232792560) // 23 s
Problem 6
What is the difference between the sum of the squares and the square of the sums?*
val numbers = 1 to 100

def square(n: Int) = n * n

val r = square(numbers.sum) - numbers.map(square).sum

assert(r == 25164150) // 1 ms
Problem 7
Find the 10001st prime.*
lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
  ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

val r = ps(10000)

assert(r == 104743) // 24 ms
Problem 8
Discover the largest product of five consecutive digits in the 1000-digit number.*
val s = """<raw input data>"""

val r = s.filter(_.isDigit).map(_.asDigit).sliding(5)
        .map(_.product).max

assert(r == 40824) // 33 ms
Problem 9
Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.*
val limit = (1 to 1000).find(n => n + math.sqrt(n) >= 1000).get

val rs = for(b <- 2 until limit; a <- 1 until b; c = 1000 - a - b
             if a * a + b * b  == c * c) yield a * b * c

val r = rs(0)

assert(r == 31875000) // 32 ms
Problem 10
Calculate the sum of all the primes below two million.*
lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
  ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

val r = ps.view.takeWhile(_ < 2000000).foldLeft(0L)(_ + _)

assert(r == 142913828922L) // 1 s
Problem 11
What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?*
val s = """<raw input data>"""

val ns = s.split("\\s+").map(_.toInt)

def m(i: Int, p: Int, c: Int): Int =
  if(c > 0) ns(i) * m(i + p, p, c - 1) else 1

def ms(xs: Seq[Int], ys: Seq[Int], p: Int) =
  ys.flatMap(y => xs.map(x => m(20 * y + x, p, 4)))

val ps = ms(0 to 19, 0 to 15, 20) ++ ms(0 to 15, 0 to 19, 1) ++ 
         ms(0 to 15, 0 to 15, 21) ++ ms(3 to 19, 0 to 15, 19)

val r = ps.max

assert(r == 70600674) // 4 ms
Problem 12
What is the value of the first triangle number to have over five hundred divisors?*
lazy val ts: Stream[Int] = 
  0 #:: ts.zipWithIndex.map(p => p._1 + p._2 + 1)

def p(t: Int) = Range(1, Int.MaxValue)
                .takeWhile(n => n * n <= t)
                .foldLeft(0)((s, n) => if(t % n == 0) s + 2 else s)

val r = ts.find(p(_) > 500).get

assert(r == 76576500) // 1 s
Problem 13
Find the first ten digits of the sum of one-hundred 50-digit numbers.*
val s = """<raw input data"""

val r = s.split("\\s+").map(_.take(11).toLong).sum.toString
        .take(10).toLong

assert(r == 5537376230L) // 2 ms
Problem 14
Find the longest sequence using a starting number under one million.*
def from(n: Long, c: Int = 0): Int = if(n == 1) c + 1 else 
  from(if(n % 2 == 0) n / 2 else 3 * n + 1, c + 1)

val r = (1 until 1000000).view.map(n => (n, from(n)))
  .reduceLeft((a, b) => if(a._2 > b._2) a else b)._1

assert(r == 837799) // 1 s
Problem 15
Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?*
def f(row: Seq[Long], c: Int): Long =
  if (c == 0) row.last else f(row.scan(0L)(_ + _), c - 1)

def r(n: Int) = f(Seq.fill(n + 1)(1L), n)

assert(r(20) == 137846528820L) // 1 ms
Problem 16
What is the sum of the digits of the number 21000?*
val r = BigInt(2).pow(1000).toString.view.map(_.asDigit).sum

assert(r == 1366) // 1 ms
Problem 17
How many letters would be needed to write all the numbers in words from 1 to 1000?*
val units = Array(0, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 
                  7, 9, 8, 8)

val tens = Array(0, 0, 6, 6, 5, 5, 5, 7, 6, 6)    

lazy val name: Int => Int = {
  case n if(n < 20) => units(n)
  case n if(n < 100) => 
    tens(n / 10) + (if(n % 10 > 0) units(n % 10) else 0)
  case n if(n < 1000) => 
    name(n / 100) + 7 + (if(n % 100 > 0) 3 + name(n % 100) else 0)
  case 1000 => 11
}

val r = (1 to 1000).map(name).sum

assert(r == 21124) // 1 ms
Problem 18
Find the maximum sum travelling from the top of the triangle to the base.*
val s = """<raw input data"""

val grid = s.trim.split("\n").map(_.split("\\s+").map(_.toInt))

def f(rows: Array[Array[Int]], bottom:Seq[Int]): Int = {
  val ms = bottom.zip(bottom.tail).map(p => p._1 max p._2)
  val ss = rows.last.zip(ms).map(p => p._1 + p._2)
  if(ss.size == 1) ss.head else f(rows.init, ss)
}

val r = f(grid.init, grid.last)

assert(r == 1074) // 2 ms
Problem 19
How many Sundays fell on the first of the month during the twentieth century?*
val lengths = Array(31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

val ls = for(y <- 1900 to 2000; m <- 1 to 12) yield
  if(m == 2)
    if (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0)) 29 else 28
  else
    lengths(m - 1)

val fs = ls.scanLeft(1)((ws, l) => (ws + l) % 7)

val r = fs.drop(12).take(1200).count(_ == 0)

assert(r == 171) // 2 ms
Problem 20
Find the sum of digits in 100!*
def f(n: BigInt): BigInt = if(n < 2) 1 else n * f(n - 1)

val r = f(100).toString.view.map(_.asDigit).sum

assert(r == 648) // 1 ms
Problem 21
Evaluate the sum of all amicable pairs under 10000.*
val ds = (0 until 10000).view
         .map(n => (1 to (n / 2)).filter(n % _ == 0).sum)

val as = ds.zipWithIndex.collect { 
  case (n, i) if n < 10000 && ds(n) != n && ds(n) == i => i
}

val r = as.sum

assert(r == 31626) // 658 ms
Problem 22
What is the total of all the name scores in the file of first names?*
val r = io.Source.fromFile("names.txt").mkString.split(",")
        .map(_.init.tail).sorted.map(_.map(_ - 64).sum)
        .zipWithIndex.map(p => p._1 * (p._2 + 1)).sum

assert(r == 871198282) // 38 ms
Problem 23
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.*
val as = (0 to 28123).map(n => (1 to (n / 2)).filter(n % _ == 0).sum)
          .zipWithIndex.filter(p => p._1 > p._2).map(_._2)

val exc = as.view.flatMap { a => 
  as.takeWhile(_ <= (28123 - a)).map(a +)
} 

val r = (1 to 28123 diff exc).sum 

assert(r == 4179871) // 5 s
Problem 24
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?*
def ps(s: String): Iterator[String] = if (s.length == 1) Iterator(s)
  else s.toIterator.flatMap(c => ps(s.filter(c !=)).map(c +))

val r = ps("0123456789").drop(999999).next().toLong

assert(r == 2783915460L) // 712 ms
Problem 25
What is the first term in the Fibonacci sequence to contain 1000 digits?*
lazy val fs: Stream[BigInt] = 
  0 #:: 1 #:: fs.zip(fs.tail).map(p => p._1 + p._2)

val r = fs.view.takeWhile(_.toString.length < 1000).size

assert(r == 4782) // 468 ms
Problem 26
Find the value of d < 1000 for which 1/d contains the longest recurring cycle.*
val ps = (2 until 1000).map(i => (1 to 2000)
         .find(BigInt(10).modPow(_, i) == 1)) 

val r = 2 + ps.indexOf(Some(ps.flatten.max)) 

assert(r == 983) // 2 s
Problem 27
Find a quadratic formula that produces the maximum number of primes for consecutive values of n.*
lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
  ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

def isPrime(n: Int) = ps.view.takeWhile(_ <= n).contains(n)

val ns = (-999 until 1000).flatMap { a => 
  (-999 until 1000).map(b => (a, b, (0 to 1000).view
    .takeWhile(n => isPrime(n * n + a * n + b)).size))
}

val t = ns.reduceLeft((a, b) => if(a._3 > b._3) a else b)

val r = t._1 * t._2

assert(r == -59231) // 6 s
Problem 28
What is the sum of both diagonals in a 1001 by 1001 spiral?*
def cs(n: Int, p: Int): Stream[Int] = 
  (n * 4 + p * 10) #:: cs(n + p * 4, p + 2)

val r = 1 + cs(1, 2).take(500).sum

assert(r == 669171001) // 1 ms
Problem 29
How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and
2 ≤ b ≤ 100?*
val r = (2 to 100).flatMap(a => (2 to 100)
        .map(b => BigInt(a).pow(b))).distinct.size

assert(r == 9183) // 17 ms
Problem 30
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.*
def max(d: Int) = math.pow(10, d).toInt - 1

def sum(n: Int) = n.toString.map(_.asDigit)
  .map(math.pow(_, 5).toInt).sum

val limit = Stream.from(1).find(d => max(d) > sum(max(d))).get

val r = (2 to max(limit)).view.filter(n => n == sum(n)).sum

assert(r == 443839) // 2 s
Problem 31
Investigating combinations of English currency denominations.*
def f(ms: List[Int], n: Int): Int = ms match {
  case h :: t =>
    if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
  case _ => 0
}

val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)

assert(r == 73682) // 15 ms
Problem 32
Find the sum of all numbers that can be written as pandigital products.*
val ms = for {
  a <- 2 to 10000; b <- 2 to 10000 / a
  m = a * b; s = a.toString + b + m
  if s.length == 9 && (1 to 9).mkString.forall(s.contains(_))
} yield m

val r = ms.distinct.sum

assert(r == 45228) // 73 ms
Problem 33
Discover all the fractions with an unorthodox cancelling method.*
val rs = for(i <- 1 to 9; j <- (i + 1) to 9; k <- 1 to 9; 
  if k * (9 * i + j) == 10 * i * j) yield (10 * i + j, 10 * j + k)

val p = rs.reduceLeft((n, d) => (n._1 * d._1, n._2 * d._2))

def gcd(n: Int, d: Int): Int = if (d == 0) n else gcd(d, n % d)

val r = p._2 / gcd(p._1, p._2)

assert(r == 100) // 5 ms

38 Comments

  1. Nicholas Sterling says:

    Pavel, thanks so much for this post — I’m learning Scala and it is interesting to look at better solutions than my own to these problems. I referred to this page in this post about a generalization of problem 1.

    I have a question, though — why do you call view() in your solutions? At least for problem 1, the code works without it — how does calling view() help?

  2. Pavel says:

    Views allow to avoid constructing intermediate results of data transformations. This improves performance and optimizes memory usage.

    Here’s an excellent explanation of how views work.

  3. sandobal says:

    Super, thank you a lot for your solutions.

  4. hbatista says:

    Great post! Thanks!

  5. MichielH says:

    Great writeup :). I started learning Scala a few days ago and your Project Euler examples have been most helpful in understanding the functional aspect of the Scala syntax. I’m looking forward to reading more of your Scala related posts in the future (this was the first one, correct?). That being said, I also cooked up an alternative solution for problem 5 and figured you might like it

    val r = (1l to 20l).reduceLeft {
      (a,b) => {
        def gcd(a: Long, b: Long): Long = if (b == 0) a.abs else gcd(b, a % b)
        (a*b) / gcd(a,b) // least common multiple
      }
    }

  6. ndesmoul says:

    I don’t know if the use of view really help, but for problem 1 the following code gives the same result and is clearly faster:

    var r = 0; for(i <- 1 until 1000; if((i % 3 == 0) || ( i % 5 == 0))){ r += i }

  7. wheaties says:

    It’s great that you’re advocating Scala use for Project Euler problems but they’ve asked that people not post the solutions to the problems on other websites. What’s the point of getting your fingers wet with the first few problems if you never really have to solve things. Granted, these problems are easy but it’s not like with a few minutes of thought they can’t be solved.

  8. Pavel says:

    >It’s great that you’re advocating Scala use for Project Euler problems but they’ve asked that people not post the solutions to the problems on other websites.

    I found no evidence that Project Euler team is opposed to sharing solutions on third-party sites. The solutions here is to demonstrate Scala in the first place, rather than Project Euler itself. I hope my examples will help people to understand Scala better (and will not be used for cheating).

  9. Pavel says:

    > I also cooked up an alternative solution for problem 5 and figured you might like it

    Nice! The code is still concise and “functional” but it runs much faster than mine.

  10. Pavel says:

    > for problem 1 the following code gives the same result and is clearly faster…

    “No vars” is the first rule of idiomatic Scala :)

    Scala encourages “functional style” of programming, with no mutable states and no side-effects. I recommend you to check “Next steps in Scala / Learn to recognize the functional style” in “Programming in Scala” book.

  11. ndesmoul says:

    Scala is an hybrid imperative/functional language, so even if the use of vals is encouraged, “No vars” is not an absolute rule.
    Quoting “Programming in Scala”, you have to prefer using val as much as possible unless “you have a specific need and justification for them”. Well in this case it is just 2 to 3 times faster (a potentially valid justification to me), and the whole method still has no side effects.
    Just to say that the pure functionnal style programming may be the most elegant, but not always the most efficient. When you deal with time critical code, it may be important to have this in mind.

  12. ndesmoul says:

    To complement my previous message, an interesting project is ScalaCLPlugin:
    https://code.google.com/p/scalacl/wiki/ScalaCLPlugin

    “The ScalaCL Compiler Plugin optimizes simple generalistic Scala loop-like calls by transforming them into equivalent while loops, which are much faster.”

    So even with pure functionnal programming, you could potentially obtain good performances.
    It could be interesting to compare the performances with and without the use of this compiler plugin.

  13. Mark says:

    Some interesting code, but I was wondering why you are using lazy vals? The examples run the same without the vals being lazy…

  14. Pavel says:

    Mark, lazy modifiers are needed to prevent “forward reference extends over definition of value” compilation error when such code is put into a method (like “main”).

  15. Mark says:

    Of course. I have a memory like a sieve. I was bitten by this a couple of years ago.

    Thanks.

  16. Rhys says:

    Hi, thanks for posting your solutions. They are very useful for comparing against my own and learning new techniques.

    I have a mundane question: how do you run these? In the REPL, in an IDE? Do you package them in individual objects that extend App, or do you have a separate object that calls them and displays the result?

  17. Pavel says:

    Rhys, I usually run such code directly, either from command line (“scala problem1.scala”) or from IntelliJ IDEA, which supports running Scala scripts.

    Additionally, I used a simple application to measure code execution time (to exclude JVM and Scala startup time).

  18. Tom Szczesny says:

    Where can I find information about the “simple application to measure code execution time”?

  19. Tom Szczesny says:

    I guess that this always works (example for problem #1):

    val timeBgn: Long = System.currentTimeMillis()
    val r = (1 until 1000).view.filter(n => n % 3 == 0 || n % 5 == 0).sum
    val timeRun = System.currentTimeMillis() – timeBgn

    assert(r == 233168)

  20. Pavel says:

    Tom, there are a lot of subtleties in benchmarking such code. Although I have used a plain main method with a preliminary “warming up” (5-10 idle iterations), you may also check something like caliper Microbenchmarking framework.

  21. [...] the “official” solutions seemed a bit complex. This was a while ago and looking at some example solutions, I think it’s just a matter of understanding some new concepts, like what a Stream[int] is [...]

  22. Micheal says:

    Hi,
    I’m looking at your solution for problem 19 and it really buggles my mind why for last 3 months you have 31 days entered in lengths array. Moreover, it gives proper result, so I guess there must be some point which I don’t understand.

    Greetigs

  23. Pavel says:

    Micheal, there was a trick bug in the solution to Problem 19, which is now fixed :) Thank you for noticing it!

  24. Stephane says:

    Problem 3 limit calculation is incorrect.
    Assuming the limit is the square root of the value leads to excluding correct values.

    Replacing “600851475143L” by “58″ is a perfect example of this. The code will return 2 as the largest prime divisor instead of 29.
    All divisors for a number n are in (1 -> n/2) not in (1 -> sqrt(n)).

  25. Pavel says:

    Stephane, that’s true. I’ve updated the solution. Thank you!

  26. [...] learn more take a look at this blog -> Scala for Project Euler. [...]

  27. [...] may also see Scala for Project Euler for more examples of Scala [...]

  28. Vitalii Tamazian says:

    Your solution for problem 1 is naive.
    Scala solution is elegant, but school math is faster :)
    What about n=1000000000?
    There is O(1) solution, just use three sums of arithmetic progressions.
    Sum of elements (1 to n), with step 3 + Sum of elements (1 to n), with step 5, minus sum of elements with step 15

    object One {
    def main(args: Array[String]) {
    sumMultiples(2)
    sumMultiples(10)
    sumMultiples(14)
    sumMultiples(15)
    sumMultiples(16)
    sumMultiples(20)
    sumMultiples(1000)
    sumMultiples(10000000)
    }

    // Solution is O(1)
    def sumMultiples(n: Long) {
    println(“Sum(%s)=%s”.format(n, sum(n, 5) + sum(n, 3) – sum(n, 15)))
    }

    // sum of arithmetic progression from divider to N-1
    def sum(N: Long, div: Long): Long = {
    val a1 = div
    val an = N – 1 – (N – 1) % div // last element of progression
    val n = 1 + (an – a1) / div // num elements of progression
    (a1 + an) * n / 2
    }

    }

  29. Pavel says:

    Hi Vitalii! Thank you for the valuable addition. However, the purpose of these solutions is to demonstrate Scala in the first place, so the problems are just a “canvas” to show the elegance and expressiveness of the language. Many times I intentionally preferred a direct and concise solution (if it performs reasonably fast) to a “math-savvy” one (I’ve added this clarification to the post).

  30. PeterX says:

    Your solution to 24 runs out of memory for me. I believe this issue is that String.flatMap is strict, so your ps generates all the permutations. This worked for me:

    def ps(s: Seq[Char]): Seq[String] =
    if(s.size == 1) Seq(s.head.toString) else s.flatMap(c => ps(s.filterNot(_ == c)).map(c +))

    ps(“0123456789″.view)(999999)

  31. PeterX says:

    Your solution to 15 is a great place to use scan:

    def f(row:List[Long], c:Int):Long =
    if (c == 0) row.last else f(row.scan(0L)(_+_), c-1)

    def r(n:Int) = f(List.fill(n+1)(1L),n)

    assert(r(20) == 137846528820L)

  32. Pavel says:

    Hi Peter! That’s a good point. We neither need to compute all the permutations, nor we need to hold all the previous values in memory. However it’s better to avoid the implicit dependency on the initial sequence implementation by using iterators (which also significantly improves the performance of the algorithm).

  33. Pavel says:

    Peter, as for the Problem 15, I agree that the “scan” method is most appropriate there. I’ve updated the solution. Thanks!

    P. S. After more than 3 years, I can easily see many more potential improvements to the solutions :)

  34. seth2810 says:

    def specialPythagoreanTriplet: BigInt = {
    @tailrec
    def prods(a: Int, b: Int): BigInt = {
    val c = 1000 – a – b
    if ((a * a) + (b * b) == (c * c)) a * b * c
    else if (a >= 1000) 0 // Not Found
    else if (b >= 1000) prods(a + 1, a + 2)
    else prods(a, b + 1)
    }
    prods(1, 2)
    }

  35. Gaurav Abbi says:

    This is regarding problem 23.

    I tried two versions of that problem:
    Version 1:
    def properDivisorsSum(n: Int): Int = (1 to n / 2).filter(n % _ == 0).sum

    val abundantNumbers = (1 until 28123).filter(x => properDivisorsSum(x) > x)

    val sumOfTwoAbundants = (for{
    x <- abundantNumbers
    y <- abundantNumbers.takeWhile(_ properDivisorsSum(x) > x)

    val asView = abundantNumbers.view

    val sumOfTwoAbundants = for{
    x <- asView
    y <- abundantNumbers.takeWhile(_ <= 28123 – x)
    }yield x+y
    (1 to 28123 diff sumOfTwoAbundants).sum

    Both versions yield results and seems to be fine.
    However, I am not clearly able to comprehend the exact optimisation of views here.

    I went through the scala documentation on Views (http://docs.scala-lang.org/overviews/collections/views.html)

    Trying to figure out where exactly the optimisation using views makes the difference.

    Here are a few thoughts:
    I believe in both cases, it is the last statement that makes the usage of "views" relevant. However, when I look at the statement,
    y <- abundantNumbers.takeWhile(_ <= 28123 – x)
    this should have already restricted my result values to less than 28123,
    unless there is a good amount of repetition of same values and that is where optimisation using views help.

    This are some ideas I have, but still feel something that is a clear picture is missing.
    could you please let me know if this understanding is correct?

  36. Gaurav Abbi says:

    For some reasons,
    versions did not come correctly:
    here it is again:
    Version 1:
    def properDivisorsSum(n: Int): Int = (1 to n / 2).filter(n % _ == 0).sum

    val abundantNumbers = (1 until 28123).filter(x => properDivisorsSum(x) > x)

    val asView = abundantNumbers.view

    val sumOfTwoAbundants = for{
    x <- asView
    y <- abundantNumbers.takeWhile(_ properDivisorsSum(x) > x)

    val sumOfTwoAbundants = (for{
    x <- abundantNumbers
    y <- abundantNumbers.takeWhile(_ <= 28123 – x)
    }yield x+y).view
    //making it view helps us compute only the results until the 28123, not after that, so we
    //are saved from computing numbers larger than 28123
    (1 to 28123 diff sumOfTwoAbundants).sum

  37. Pavel says:

    Hi Gaurav,

    The whole point of using “views” is to avoid allocation of intermediate collections, and thus to save heap memory and to relieve GC from the excessive work.

    We may consider using views when:
    * collection size is relatively large,
    * there’s no need for random-access or re-iteration.

    The primary statement that relies on a view is the sumOfTwoAbundants calculation: for every abundant number we generate an additional _sequence_ of numbers (because the for-yield statement is translated into .flatMap call under the hood), so the total length of the resulting sequence is about (abundantNumbers.length ^ 2) / 2 (the exact length is 24294140).

    Unless we use a view, we have to hold all those intermediate numbers in memory. As Scala collections don’t use specialization, every instance of Integer occupies 16 bytes of memory (VM implementation-dependent), requiring about 370 MB of heap memory, which, aside from being pointless, leads to an OutOfMemoryError under default JVM heap size (256 MB).

    When we call .view beforehand, we guarantee that all subsequent monadic transformations (like .flatMap) of the sequence will be resulted in just another “view”, so they can be performed in constant space.

    Another option here is to replace .view with .toSet, which can also help to reduce the number of allocated integers.

  38. Gaurav Abbi says:

    Hi Pavel,
    Thanks for the reply. It helps.

Leave a Reply