Project Euler problem 001

The statement to the first problem is as follows:

Hands-on

I am trying to use a lisp dialect, specifically, racket. I was wondering if I should have started with common lisp but I believe that racket is a good starting point.

I'll start by breaking the problem into parts. The first part being to determine if a given number $n$ is multiple of 3 and 5. To know if a number is multiple of another one can just compute the modulo $n \pmod m$, if it equals 0 then $n$ is a multiple of $3$.

I wrote one function for each case:

(define (multiple-of-3? n)
  (= 
    (modulo n 3)
    0))

(define (multiple-of-5? n) 
  (=
    (modulo n 5)
    0))

Now, with a way to determine if a given number $n$ is multiple of 3 or 5, it is possible to write a recursive function to sum all numbers in the range $[start,stop)$ as long as both conditions are met. The right-side of the range is not included because the statement of the problem mentions that the sum only includes the numbers below a limit.

The function sum-of-multiples has 3 arguments, the starting and ending points of the sum, start and stop, respectively, and an optional argument acc which is an accumulator where the sum of those numbers that are multiples of 3 and 5 are added up:

(define (sum-of-multiples start stop [acc 0])
  (if (= start stop)
      acc
      (if (and
           (not (multiple-of-3? start))
           (not (multiple-of-5? start)))
          (sum-of-multiples stop (add1 start) acc)
          (sum-of-multiples stop (add1 start) (+ acc start)))))

On each recursion, the value of start is modified adding 1 to it as to emulate the iteration process done in not-functional programming languages. Only when the condition is fulfilled is when the value of the accumulator acc is updated on the following call to sum-of-multiples.

By this point I noticed something seemed weird in the structure of sum-of-multiples, the logic was a little bit messy. Even though the result of evaluating the function with the test case gave the correct result:

> (sum-of-multiples 0 10)
23

Let us compute the solution to the problem before refactoring the functions:

> (sum-of-multiples 1 1000)
233168

The first change is to remove the explicit dependency of sum-of-multiples changing start to be an optional argument, and declaring it to start at 1 instead of 0:

(define (sum-of-multiples stop [start 0] [acc 0])
  (if (= start stop)
      acc
      (if (and
           (not (multiple-of-3? start))
           (not (multiple-of-5? start)))
          (sum-of-multiples stop (add1 start) acc)
          (sum-of-multiples stop (add1 start) (+ acc start)))))

Now, allow me to give the propositional logic another look...

okay so I was right but I can make it neater. And sum-of-multiples will look like

(define (sum-of-multiples stop [start 0] [acc 0])
  (if (= start stop)
      acc
      (if (not (or (multiple-of-3? start) (multiple-of-5? start)))
          (sum-of-multiples stop (add1 start) acc)
          (sum-of-multiples stop (add1 start) (+ acc start)))))

I still don't like to have two functions that do se same thing multiple-of-3? and multiple-of-5?. One single function could do the trick:

(define (is-multiple? x y)
  (=
   (modulo x y)
   0))

With this change, the function sum-of-multiples will look as

(define (sum-of-multiples stop [start 0] [acc 0])
  (if (= start stop)
      acc
      (if (not (or (is-multiple? start 3) (is-multiple? start 5)))
          (sum-of-multiples stop (add1 start) acc)
          (sum-of-multiples stop (add1 start) (+ acc start)))))

... and I think it is beautiful.

Testing it with the test case and the problem case we get the same results:

> (sum-of-multiples 10)
23
> (sum-of-multiples 1000)
233168

In racket there is a function very handy to remove the two calls of is-multiple? inside the or, it is ormap. For example, the function is-multiple? can be mapped to the elements of a list, in this case 3 and 5, to know if a given number is multiple of each of them individually:

> (map (lambda (x)
	(is-multiple? 6 x)) '(3 5))
'(#t #f)

Clearly, 6 is multiple of 3 but not of 5. But it is only necessary that the number we are testing, in this case is 6, is multiple of one of them not all. This is were ormap is helpful, the documentation explains that (ormap f (list x y z)) is equivalent to (or (f x) (f y) (f z)) where f is a function and x, y, z are arguments to be applied to that function. Thus, the refactoring will lead to:

(define (sum-of-multiples stop [start 0] [acc 0])
  (if (= start stop)
      acc
      (if (not (ormap (lambda (x)
                        (is-multiple? start x)) '(3 5)))
          (sum-of-multiples stop (add1 start) acc)
          (sum-of-multiples stop (add1 start) (+ acc start)))))

And the function can be made more generic is a new argument is provided to hold the list of factors:

(define (sum-of-multiples factors stop [start 0] [acc 0])
  (if (= start stop)
      acc
      (if (not (ormap (lambda (x)
                        (is-multiple? start x)) factors))
          (sum-of-multiples factors stop (add1 start) acc)
          (sum-of-multiples factors stop (add1 start) (+ acc start)))))

~