# Finding the sum of all the multiples of 3 or 5 below 1000

As a Lisp (and functional programming) newbie, I wrote the following code that finds the sum of all the multiples of 3 or 5 below 1000, and I suspect that it is lousy:

(defun multiple-of-3-or-5 (x)
(or (eq (mod x 3) 0) (eq (mod x 5) 0)) )

(defun generate-list (min max)
(cond ((> min max) nil)
(t (cons min (generate-list (+ min 1) max )))))

(defun my-sum (my-list)
(cond ((atom my-list) 0)
(t (+ (cond ((multiple-of-3-or-5 (car my-list)) (car my-list))
(t 0))
(my-sum (cdr my-list))))))


Any general advice is most welcome. Specifically, I have these questions (other than what you could say):

1. I had to extend the stack multiple times (using LispWorks) to get a result. Is my use of recursion wrong?
2. Should I prefer iterative approach over recursion in Lisp too? (as in imperative languages)
3. Should I use the loop macro if I am to solve it in iterative fashion?
-
Major code fail: this doesn't print Fizz or Buzz! –  Kyle Hale May 19 at 14:58
–  Anonymous May 19 at 15:11

Is my use of recursion wrong?

It's not wrong, but it's unnecessarily complex. There's no need to create a list and recurse over it when you could simply iterate over the numbers.

Should I prefer iterative approach over recursion in Lisp too? (as in imperative languages)

Iteration is perfectly acceptable in functional languages! Functional programmers talk about recursion a lot, because it's more flexible (and thus more powerful) than iteration, but we use iteration too, when we don't need that power. This is why most functional languages have plenty of iteration tools built in — Common Lisp's mapcar, some, reduce, loop and do, for example.

Use iteration when it's the simplest solution, and recursion when you need it.

Should I use the loop macro if I am to solve it in iterative fashion?

Sure, loop is the simplest way to do this, so it's what most Common Lispers would do. It's a bit complex for beginners, though; do might be easier to learn.

generate-list is traditionally called range or iota. Rather than define it yourself, you can get it from a library such as Alexandria.

The explicit recursion in my-sum is not necessary. It's simpler (and clearer) to use the standard sequence functions remove-if-not and reduce instead:

(reduce #'+ (remove-if-not #'multiple-of-3-or-5 (iota 1000)))


The best way to test for the end of a list is endp, not atom. (It also signals an error on improper lists.)

(1+ min) is a little clearer than (+ min 1).

-
Thanks! This is the kind of advice I am looking for. –  henginy May 19 at 7:39
1. You are not using tail recursion in my-sum, so the compiler cannot easily turn it into iteration.

2. It depends on the specific problem; in this case I would probably do it iteratively.

3. Sure, loop is useful and convenient.

Here is my attempt:

(defun multiple-of-3-or-5 (x)
(or (zerop (mod x 3))
(zerop (mod x 5))))
(defun my-sum (from to)
(loop :for i :from from :to to
:when (multiple-of-3-or-5 i)
:sum i))

-
Or without loop: (let ((sum from)) (dotimes (i to) (when (multiple-of-3-or-5 i) (setq sum (+ sum i)))) sum) –  Drew May 19 at 2:00
@Drew: (incf sum i) –  Anonymous May 19 at 4:22
@Anonymous: Yes, of course. Been using older Emacs-Lisp versions too long. –  Drew May 19 at 4:26
Thanks (esp. for pointing out tail recursion). –  henginy May 19 at 7:37

I agree with sds's post. In addition, you should note that eq does not guarantee to return true for two equal numbers (see, especially, the (let ((x 5)) (eq x x)) case). You should use zerop to test if a number is zero (and = for comparing numeric equality in general).

-
That would take me long to discover, thanks! –  henginy May 19 at 7:38
But if they're both numbers of the same type, then eql is OK. –  Joshua Taylor Jun 22 at 19:21

You're solving the problem inefficiently; in the same way that you can mentally figure out in a few seconds that the sum of every number from 1 to 100 inclusive is 5050, you can do the same here:

999/5 = 199 instances, divided by 2 is 99 (plus 500, the half-way mark)

5 + 995 = 1000 sum of opposite numbers

1000 sum * 99 instances = 99,000

999/3 = 333 instances, divided by 2 is 166 (plus 501, the half-way mark)

3 + 999 = 1002 sum of opposite numbers

1002 sum * 166 instances = 166,332

And now to allow for where 3 and 5 are double counted:

999/5*3 = 66 instances, divided by 2 is 33

15 + 990 = 1005 sum of opposite numbers

1005 sum * 33 instances = 33,165

Answer = 99,000+500 + 166,332+501 - 33,165

This algorithm doesn't scale well beyond a handful of numbers, but works very well for large ranges.

-
You are correct in pointing out that this is a problem that can be solved analytically, but does the calculation you offer consider the fact that every 15th integer is a multiple of both 3 and 5? –  Iwillnotexist Idonotexist May 19 at 4:30
Well spotted. Fixed. –  Josh May 19 at 6:06
Thanks for the improvement in the algorithm but my focus is really on the code itself. –  henginy May 19 at 7:34