Sum of multiples of 3 or 5 below 1000 in Scala

Question

I'm in the process of learning Scala, and started working through a series of coding puzzles that I've done previously in other languages.

For example, this solution, coded in Erlang:

sum_multiples(Max, Max, Acc) -> io:format("The sum of all the multiples of 3 or 5 below ~p: ~p~n", [Max, Acc]);
sum_multiples(Current, Max, Acc) when (Current rem 3 == 0) or (Current rem 5 == 0) -> sum_multiples(Current + 1, Max, Current + Acc);
sum_multiples(Current, Max, Acc) -> sum_multiples(Current + 1, Max, Acc).

Now, doing this same problem in Scala, I wrote this:

val max = 1000
println(s"The sum of all the multiples of 3 or 5 below ${max}: " + sum_multiples_recursive(1, max, 0))
def sum_multiples_recursive(current: Int, max: Int, acc: Int): Int = {
  if(current < max){
    if(current % 3 == 0 || current % 5 == 0){
      sum_multiples_recursive(current + 1, max, current + acc)
    } else {
      sum_multiples_recursive(current + 1, max, acc)
    }
  } else {
    acc
  }
}

I'd like to see what an experienced Scala coder might write, what Scala idioms might come into play.

Answer 1

In the Scala solution as in the Erlang solution, the accumulator is pointless. For max = 1000, you don't necessarily have to be concerned about tail recursion, and you could just write it without an accumulator:

def sumMultiplesRecursive(from: Int, to: Int): Int = {
    if (from >= to) {
        0
    } else if (from % 3 == 0 || from % 5 == 0) {
        from + sumMultiplesRecursive(from + 1, to)
    } else {
        sumMultiplesRecursive(from + 1, to)
    }
}

Note that the sum_multiple_recursive name, with underscores, does not follow the Scala naming convention. It is not so helpful to mention that it works recursively, but it would also be useful to describe what you mean by "multiples".

The from and to parameters, together, could constitute a Range. If you are going to use a Range, then you might as well take advantage of its capabilities:

def sumMultiplesOf3Or5(range: Range): Int = {
    range.filter(n => n % 3 == 0 || n % 5 == 0).sum
}

val max = 1000;
println(s"The sum of all the multiples of 3 or 5 below ${max}: " + sumMultiplesOf3Or5(1 until max));

Answer 2

Some other tips not mentioned in the accepted answer:

String Interpolation

Originally you had the following code to print your results:

println(s"The sum ... below ${max}: " + sum_multiples_recursive(1, max, 0))

To make your style more consistent this can be rewritten as:

println(s"The sum ... below $max: ${sum_multiples_recursive(1, max, 0)}")

Basically you only need to wrap functions in curly braces and not values.

For max > ~1e6

With a bit of limited testing your current solution seems to give wrong answers when max is around one million. Also, while your algorithm scales linearly with regards to max there is an algorithm that runs in constant time with regards to max. For an explanation of the math behind it see here.

import scala.math.abs

def gcd(a: Int, b: Int): Int = 
  if (b == 0) abs(a)
  else        gcd(b, a % b)

def lcm(a: Int, b: Int): Int = 
  abs(a * b) / gcd(a, b)

def f(a: Int, b: Int, max: Int): Int = {
  def g(x: Int): Int = {
    val k = (max - 1) / x
    k * (k + 1) / 2 
  }
  val x = a * g(a)
  val y = b * g(b)
  val u = lcm(a, b)
  val z = u * g(u)
  x + y - z
}