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 5
If 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.
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 and below a certain number, we sum up the found multiples up to and including a certain number. So let be a method solving the problem for summing up all multiples of and up to and including . Then, for finding the sum of all multiples below , we just need to call .
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.
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 or . If so, the integer is added to the total sum.
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 , sum up all integers for which holds that and either or (this is a mathematical shorthand notation for is a divisor of or is a divisor of . 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 equals or is larger than . If equals , then the sum is equal to since is not a divisor of and is also not a divisor of . If is larger than , then the solution is the solution to plus if or . The takes care of solving the problem up to so we are only left with checking itself.
Now we have thought out all of this, the code gets relatively small (and functional):
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 .
The solution to this problem is the following. Define . Define . Note that and are equal! If I would add up and , I get and this is thus equal to (or or , it is all the same). So . And that means that . A concrete example: find the sum of . This thus equals (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 and up to and including an integer . If we would write this sum out, we would get . Note that we counted the multiples of both and double! The smallest such a multiple is , so we have to remove all multiples of . The sum now becomes . Now we can transform this problem into the problem of Gauss. The sum simply equals . 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 divided by (or or ) and then divide by (or or ). Now we have all the ingredients for the better approach. The resulting code is shown below.
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.
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.