Project Euler problem 1

Project Euler problem 1 asks:

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.

Download p1.m