## Thursday, March 24, 2011

### Project Euler problem 1

Add all the natural numbers below one thousand that are multiples of 3 or 5.

We start by declaring the module and defining its interface, which is standard boilerplate for the main module of a program:

```:- module p1.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.```

In our implementation, we will utilize the `int` and `solutions` modules from the standard library:

```:- implementation.
:- import_module int, solutions.```

The integers provided by `int` are guaranteed to be at least 32-bit and so will be large enough for this problem. `solutions` provides the `aggregate` function which we will use to sum the results.

First let’s define the numbers we’re interested in by defining a predicate, aptly named `multiple_of_3_or_5_below_1000`. It is a predicate of one argument, which, when used as an output (`::out`), produces zero or more results (`is nondet`).

`:- pred multiple_of_3_or_5_below_1000(int::out) is nondet.`

Implementing this predicate is easy using the builtin `nondet_int_in_range` predicate to generate integers, and `rem` to check that the remainder is zero when divided by 3 or 5:

```multiple_of_3_or_5_below_1000(I) :-
nondet_int_in_range(1, 999, I),
(I rem 3 = 0; I rem 5 = 0).```

We can then define the problem solution `p1` as the sum of the multiples using builtins `aggregate` and `plus`:

`p1 = aggregate(multiple_of_3_or_5_below_1000, plus, 0).`

The type of `p1` can be inferred by the compiler as a function of zero arguments returning an `int`.

Because `plus` is associative and commutative, we could use the `unsorted_aggregate` predicate instead to avoid the overhead of sorting the solutions first (since the order doesn’t matter). However, it turns out that the overhead is negligible in this program, so we can stick with the `aggregate` function for the sake of clarity.

Lastly, print the result. The IO state is threaded using DCG notation.

`main --> print(p1), nl.`

We can then build the program using `mmc --infer-all --make p1`. The resulting program runs in about 100 ms on my dual-core 1.6 GHz machine.

1. 