# Multiples of 3 and 5

Project Euler has a huge collection of interesting puzzles that test mathematical insight and programming skills. You can make your own free account on their website and work on puzzles using any language you choose. I’ve made an account to track my progress implementing solutions in Standard ML for this blog.

Let’s give the first problem a try. For convenience it’s quoted below.

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.

Consider the example. How is the set of multiples $\lbrace 3,5,6,9 \rbrace$ constructed from base numbers $3$ and $5$ and an upper bound of $10$? Easy.

### Solution Strategy

1. Build the set of multiples of $3$ up to but not including $10$. $$\text{mults}(3,10) = \lbrace 3,6,9\rbrace$$
2. Do the same for the multiples of $5$. $$\text{mults}(5,10) = \lbrace 5\rbrace$$
3. Take the union of the two sets. The result is the set of natural numbers below 10 that are multiples of 3 or 5. $$\text{mults}(3,10) \cup mults(5,10) = \lbrace 3,5,6,9\rbrace$$
4. Now finish the whole problem off by taking the sum of the union’s elements. $$\sum \left( \text{mults}(3,10) \cup \text{mults}(5,10)\right) = 23$$

We’ve broken down the tasks, and that goes a long ways toward programming a solution in any language.

### Implementing Sets

The SML Basis Library doesn’t have a built-in set data structure, so we’ll have to work with what it provides. The built-in List structure supports several important properties of sets:

1. Zero or more elements of type X can be stored in an X list. In our case we’re interested in the int list.
2. Any two X list values can be concatenated together using @. The result is a new X list with all the elements of the first list and then all the elements of the second list. Which set operation comes to mind here?

But there’s a problem. A set of int values can’t have duplicates, yet there’s no limit to the number of repeat elements in an int list. As we try using List structures as sets keep your eyes out for places where duplicate values might infect our sets.

### Implementing $\text{mults}$

Our strategy depends on a function called $\text{mults}$ to generate a bounded list of multiples. Here’s how you could do it in SML.

Check out the local helper function called build_multiples. This nested function continually calls itself until the current_mult is greater than or equal to the user-specified max, at which point it returns the list_so_far. Each time build_multiples calls itself, the list_so_far has one more element than it did before: the current_multiple. When we first call multiples_of, we don’t yet know the multiples of n, but we do know that that the first multiple we want is n. Hence the outer function calls the helper function with n as the current_mult and the empty list [] as the list_so_far.

Now it’s easy to evaluate $\text{mult}(3,10)$ in SML:

You may have noticed the result ordering doesn’t match $\lbrace 3,6,9\rbrace$, but recall that we’re treating these lists are sets and order doesn’t matter in sets. We only care that the list contains each of the expected elements exactly once.

### Implementing Set Union Operator

In step 3 of our above strategy, we rely on the union operator $\cup$. The union of two sets is simply a set containing all the elements of both sets. We’re using lists, so somehow we need to combine the elements of two lists into one list. Recall the list appending operator @?

So we can define union like this, right?

Not quite. Do you see why? If any element is in both set1 and set2 the element would be repeated in the resulting set. Not good.

To overcome this wrinkle, we have to return a list of the unique elements in set1 @ set2. The unique_elements function filters out redundancies.

Now we can correctly implement union.

### Implementing Summation

The final step in our strategy sums all the elements of the set built up in previous steps. Again, in SML we’re using lists so the question becomes how do we find the sum of the integers in a list?

Much like multiples_of and unique_elements, sum has an inner helper function that processes each element of the provided list and builds up the desired result. This pattern is incredibly common in languages like SML, so you’ll see a lot of it. In fact, the pattern is so common that there’s a simpler way to do it, but I’ll save that for a future post.

### Solution

We’ve implemented all the tools necessary to calculate the answer, so let’s figure out it. First, let’s verify that we get the expected result for the example:

It works! Great, so what’s the real answer? It’s easy to find now.

Sorry, I’m not going to just give it away. I already gave you the tools. Now go try it.

Looking for more of a challenge? Simplify the function implementations using what’s available in the SML Basis Library.