Lispy code? Sum multiples of 3 or 5 up to 1000

Question

I've started learning Lisp one more time (I seem to do this every couple years); my experience is with C, basically. I attempted to solve the Project Euler problem 1:

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.

My solution to the problem is below.

Please suggest improvements, style changes, indentation, commenting, naming of "objects", ...

(defun multiple-of-3-or-5p (n)
 "predicate for multiple of 3 or 5"
 (cond ((= 0 (rem n 3)) t)
 ((= 0 (rem n 5)) t)
 (t nil)))
(defun sum35 (n)
 "sum all multiples of 3 or 5 up to n (including n)"
 (cond ((= n 0) 0)
 (t (+ (if (multiple-of-3-or-5p n) n 0) (sum35 (- n 1))))))
;; in the repl use
;; (sum35 999)
(defun predicate-sum (predicate n)
 "sum integers up to n (including n) that match the predicate"
 (cond ((= n 0) 0) ; stop recursion
 (t (+
 (if (funcall predicate n) n 0) ; add n or 0 and
 (predicate-sum predicate (- n 1)))))) ; the recursed sum to (n - 1)
;; in the repl use
;; (predicate-sum 'multiple-of-3-or-5p 999)

Other than "stuff" relevant to the code above, I came across a few question while working on this problem.

1. What is the natural Lispy way to define upper boundaries? Include or exclude the specific value? Ie, if you see (summation 3 6) you think 3+4+5 or 3+4+5+6?
2. Is there a standard way to make a list of numbers 0 to 1000 (999)? Something like (make-list 0 1000)?

Thanks in advance

• slepic: This can be done in constant time, by multiplying formula for sum of arithmetic series by 3 or 5.
• slepic: Assuming negative multiples are ignored otherwise the result Is always negative infinity.
• slepic: 3 * arsum(1, 1000/3) + 5 * arsum (1, 1000/5) - 15 * arsum(1, 1000/15)
• bipll: @slepic Unsigned infinity if you don't count zero; undefined otherwise.
• slepic: @bipll you are wrong, adding any Infinite set of negative numbers together Is Always defined And Always negative Infinity. Even if you also add any finite set of nonnegative numbers (including zeroes).

Answer 1

Conditions

In general something like "if a then true else false" can be simplified as "a". So your first function could be simplified as:

(defun multiple-of-3-or-5p (n)
 "predicate for multiple of 3 or 5"
 (or (= 0 (rem n 3)) (= 0 (rem n 5))))

Cond with only two cases

A cond with only two cases is written preferibly as an if. For instance:

(defun sum35 (n)
 "sum all multiples of 3 or 5 up to n (including n)"
 (if (= n 0)
 0
 (+ (if (multiple-of-3-or-5p n) n 0) (sum35 (- n 1)))))

Use the operators 1+ and 1- instead of adding or subtracting 1

The usual way of writing (- n 1) is (1- n).

Recursion and Iteration

Common Lisp has a very powerful iteration construct, loop (see for instance here for a detailed discussion), that can make simpler to write cases like in the last two functions. For instance:

(defun sum35 (n)
 "sum all multiples of 3 or 5 below n"
 (loop for i below n
 when (multiple-of-3-or-5p i) sum i))
; (sum35 1000)

Analogously,

(defun predicate-sum35 (predicate n)
 "sum integers up to n (including n) that match the predicate"
 (loop for i below n
 when (funcall predicate i) sum i))
; (predicate-sum35 #'multiple-of-3-or-5p 1000)

(note the use of #' to get a function).

Finally, to answer your last two questions:

1. The "natural" way in Common Lisp is to exclude the last value, as in all predefined functions that specify a range (for instance to get a substring with the first two characters of "foo", you can write (subseq "foo" 0 2), that returns "fo", with the index starting from 0).

2. A primitive function does not exists. You can obtain a list of this kind very easily by using loop, for instance: (loop for i below 1000 collect i).

Edited

As suggested in a comment by @slepic, the algorithm is not the best one, since it checks for all the numbers from 0 to n, while one could simply sum directly all the multiples. Here is a possible solution:

(defun sum35 (n)
 (flet ((sum-m (k)
 (loop for i from k below n by k sum i)))
 (+ (sum-m 3) (sum-m 5) (- (sum-m 15)))))

Or you can use a direct formula, like that in another comment.

• slepic: Good suggestions. Unfortunately they are only cosmetic changes to the OP's brute force solution. You both missed the point of project Euler. It's more about thinking then it is about coding.
• slepic: You don't even have to loop to get the sum of arithmetic series, there is a simple formula for this: n * (a_1 + a_n) / 2, where a_1, is the first element of the series, a_n is the last element of the series and n is number of elements of the series. In our case a_1=1, n=round_down((1000-1)/(3 resp. 5 resp, 15)), a_n=n (that is 333 resp. 199 resp. 66). So it is 3 * (334 / 2 * 333) + 5 * (200 / 2 * 199) - 15 * (66 / 2 * 67). Sure you can generalize to any upper limit, not just 1000.