Project Euler using Scala： Problem

In this last post I gave a short introduction to Scala. In this article, I will show you the strength of Scala for solving one of the mathematical problems posted on Project Euler. The problem description is as follows:

Multiples of 3 and 5If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

I will first show you a naive approach and then I will show you a better approach.

Introduction

We will slightly adapt the problem to make it more easy for us to write a solution for the problem. Instead of summing the multiples of $latex 3$ and $latex 5$ below a certain number, we sum up the found multiples up to and including a certain number. So let $latex solve(m)$ be a method solving the problem for summing up all multiples of $latex 3$ and $latex 5$ up to and including $latex m$. Then, for finding the sum of all multiples below $latex 10$, we just need to call $latex solve(9)$.

Naive approach

There are two flavours for a naive solution to this problem. The first one is the imperative style in which a variable is changed over time. I would discourage this approach by giving you also a functional version of the same code. You can see that the functional version is more clear and is shorter than the imperative version.

Imperative

A lot of people are used to imperative programming. Note that you do not know the state of the variable directly if you look at it. This makes debugging cumbersome. The naive approach simply goes through all the integers and checks whether the integers are a multiple of either $latex 3$ or $latex 5$. If so, the integer is added to the total sum.

/**
 * Sum up all integers x (for 1 <= x <= m) for which holds that x is divisible by 3
 * or x is divisible by 5. An imperative style is used here.
 *
 * @param m the upperbound for the check
 * @return sum of all integers x (1 <= x <= m) for which holds that x % 3 == 0 or x % 5 == 0
 */
def solveNaivelyImperative(m: Int): Int = {
 // Since sum is a var, we don't know how it will change over time
 var sum = 0
 for (i <- 1 to m) {
 // Here the magic happens to our sum
 if (i % 3 == 0 || i % 5 == 0) {
 sum += i
 }
 }
 sum
}

Imperative naive approach

Functional

More thinking generally means better and shorter code. So lets first think of our functional approach. Let’s first define the problem mathematically. For a given integer $latex m$, sum up all integers $latex x$ for which holds that $latex 1 le x le m$ and either $latex 3

x$ or $latex 5

x$ (this is a mathematical shorthand notation for $latex 3$ is a divisor of $latex x$ or $latex 5$ is a divisor of $latex x$. The first thing to do, is to apply a technique called command-and-conquer. We look at the problem and split it up into smaller subproblems. Either $latex m$ equals $latex 1$ or $latex m$ is larger than $latex 1$. If $latex m$ equals $latex 1$, then the sum is equal to $latex 0$ since $latex 3$ is not a divisor of $latex 1$ and $latex 5$ is also not a divisor of $latex 1$. If $latex m$ is larger than $latex 1$, then the solution is the solution to $latex solve(m – 1)$ plus $latex m$ if $latex 3

m$ or $latex 5

m$. The $latex solve(m – 1)$ takes care of solving the problem up to $latex m – 1$ so we are only left with checking $latex m$ itself.

Now we have thought out all of this, the code gets relatively small (and functional):

/**
 * Sum up all integers x (for 1 <= x <= m) for which holds that x is divisible by 3
 * or x is divisible by 5. A functional style is used here.
 *
 * @param m the upperbound for the check
 * @return sum of all integers x (1 <= x <= m) for which holds that x % 3 == 0 or x % 5 == 0
 */
def solveNaivelyFunctional(m: Int): Int = {
 // Note that the functional solution is much cleaner and smaller than the imperative solution
 if (m == 1) return 0
 val partialSum = if (m % 3 == 0 || m % 5 == 0) m else 0
 solveNaivelyFunctional(m - 1) + partialSum
}

Functional naive approach

Better approach

One word. Gauss. Gauss was a brilliant mathematician and solves the following problem (which will lead us to an even better solution to our problem).

Find the sum of $latex 1, 2, …, k$.

The solution to this problem is the following. Define $latex S = 1 + 2 + … + k$. Define $latex T = k + (k – 1) + … + 1$. Note that $latex S$ and $latex T$ are equal! If I would add up $latex S$ and $latex T$, I get $latex (1+k) + (1+k) + … + (1+k)$ and this is thus equal to $latex 2S$ (or $latex 2T$ or $latex S+T$, it is all the same). So $latex 2S = k times (k + 1)$. And that means that $latex S = frac{1}{2} times k times (k + 1)$. A concrete example: find the sum of $latex 1, 2, …, 100$. This thus equals $latex S = frac{1}{2} times 100 times 101 = 5050$ (and you don’t have to type all the numbers into your calculator!).

How can we transform our problem in terms of the former problem? As described in the functional naive approach section, we have to find the sum of multiples of $latex 3$ and $latex 5$ up to and including an integer $latex m$. If we would write this sum out, we would get $latex 3+6+9+12+15… + 5+10+15+…$. Note that we counted the multiples of both $latex 3$ and $latex 5$ double! The smallest such a multiple is $latex 15$, so we have to remove all multiples of $latex 15$. The sum now becomes $latex 3+6+9+…+5+10+15+…-15-30-45-…$. Now we can transform this problem into the problem of Gauss. The sum simply equals $latex 3 times (1+2+3+…) + 5 times (1+2+3+…) – 15 times(1+2+3+…)$. There is a problem here. Up to what number should we multiply? The largest such a number can be found be subtracting the remainder of $latex m$ divided by $latex 3$ (or $latex 5$ or $latex 15$) and then divide by $latex 3$ (or $latex 5$ or $latex 15$). Now we have all the ingredients for the better approach. The resulting code is shown below.

/**
 * Sum up all integers x (for 1 <= x <= m) for which holds that x is divisible by 3
 * or x is divisible by 5. A functional style is used here and some mathematics are
 * used which makes this solution more elegant than the naive solution.
 *
 * @param m the upperbound for the check
 * @return sum of all integers x (1 <= x <= m) for which holds that x % 3 == 0 or x % 5 == 0
 */
def solveSmart(m: Int): Int = {
 def sumGauss(n: Int): Int = n * (n + 1) / 2
 def countDivisors(d: Int): Int = (m - m % d) / d
 3 * sumGauss(countDivisors(3)) + 5 * sumGauss(countDivisors(5)) - 15 * sumGauss(countDivisors(15))
}

Why is this code better than the functional approach? Note that it saves an enormous amount of time since this approach does not need to scan through all the integers! It are simply a few calculations (at which a computer is good at). All the code (the naive approach and the better approach) can be found on GitHub.

Testing the answers

This section is optional. I will describe my Scala tests and why it is useful to test. In the problem, an answer is given to a problem with a few numbers. In the example, a generalization is asked for very large numbers. If I have a general solution, the solution to the small problem must still hold. This is a sanity check whether the general solution makes sense. The testing code is shown in the next code snippet.

class Solution extends FlatSpec with Matchers {

 // Check the different solvers
 "solvers" should "solve subproblem" in {
 checkSolutions(new Solver().solveSmart)
 checkSolutions(new Solver().solveNaivelyFunctional)
 checkSolutions(new Solver().solveNaivelyImperative)
 }

 // Check a number of problems
 def checkSolutions(method: (Int) => Int): Unit = {
 // The multiples of 3 and 5 for integers x (1 <= x <= 9) should sum up to 23
 shouldSolve(method, 9, 23)
 // The multiples of 3 and 5 for integers x (1 <= x <= 999) should sum up to 233168
 shouldSolve(method, 999, 233168)
 }

 /**
 * Check whether a method produces the correct solution to a given problem.
 *
 * @param method the method to check
 * @param m m such that for all integers x (1 <= x <= m) the given method should produce the specified solution
 * @param solution the solution to the problem (the sum of all integers x (1 <= x <= m) for which holds that x
 * is divisible by 3 or by 5)
 */
 def shouldSolve(method: (Int) => Int, m: Int, solution: Int): Unit = {
 assert(method(m) == solution)
 }

}

Conclusion (TL;DR)It is easy to come up with a naive (imperative) approach. A functional approach requires some thinking and a mathematical approach requires even more thinking. The longer you think, the cleaner and the shorter your code becomes.