gistfile1.lisp

;; ProjectEuler.net
;;
;; Multiples of 3 and 5
;; 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.

(defun multiple-of-p (y x)
  (let ((r (mod x y)))
    (if (eq 0 r) t nil)))

(defun find-next-multiple (multiple value)
  (if (multiple-of-p multiple value) value (find-next-multiple multiple (1+ value))))

(defun collect-multiples-from-to (multiple limit)
  (do* ((value multiple (find-next-multiple multiple (1+ value)))
        (value-list (list multiple) (push value value-list)))
       ((>= value limit) (cdr value-list))))

(defun sum-two-multiples-up-to (x-multiple y-multiple limit)
  (reduce #'+ (union (collect-multiples-from-to x-multiple limit) (collect-multiples-from-to y-multiple limit))))

(defun answer ()
  (sum-two-multiples-up-to 3 5 1000)) ;  233168


;; Shorter version

(defun answer (x y limit)
  (loop for i
        from 1 to (1- limit)
        summing (if (or (eq 0 (mod i x))
                        (eq 0 (mod i y)))
                    i 0))) ; 233168

;; Tail Recursive version

(defun sum-multiples (multiple-x multiple-y value sum limit)
  (if (< value limit)
    (if (or (zerop (mod value multiple-x)) (zerop (mod value multiple-y)))
      (sum-multiples multiple-x multiple-y (1+ value) (+ sum value) limit)
      (sum-multiples multiple-x multiple-y (1+ value) sum limit))
    sum))

(defun answer ()
  (sum-multiples 3 5 0 0 1000)) ; 233168