Euler project problem #1

gistfile1.clj

; Euler problem #1. Sum of integers between 1 and N which are
; divisible by i, j, k, ..., or l.
;
; The sum 1+2+3+...+n = (n^2 + n)/2, call this sum-range(n).
;
; Then the sum of i+2i+3i+...+qi = i * sum-range(floor(n/i)), where
; qi is the greatest multiple of i such that i <= n.
;
; For n=20, f(3,5) involves summing the rows in a table:
;
;     1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 
;   +-----------------------------------------------------------+
; 3 |       3        6        9       12       15       18      | 
; 5 |             5             10             15             20|
;   +-----------------------------------------------------------+
;
; First thought is to sum the first row (the numbers between 1 and
; 20 which are multiples of 3) and the second row (numbers between
; 1 and 20 which are multiples of 5). But this is not correct
; because 15 double-counted. This is because 15 is a multiple of
; both 3 and 5, so it must appear in both rows. This implies that
; all numbers between 1 and n which are multiples of 3 and 5 must
; be subtracted from the final sum, like this:
; 
;           f(3,5) = f(3) + f(5) - f(3*5)
;
; But this method only works because 3 and 5 are relatively prime.
; What is actually required is:
;
;           f(3,5) = f(3) + f(5) - f(lcm(3,5))
;           
; where lcm is the least common multiple function. Now suppose we
; were to add all the multiples of 7 to this sum. First, we have
;
;         f(3,5,7) = f(3,5) + <something>
;
; where <something> is the sum of multiples of 7 that have not
; already been counted by f(3,5), so:
;
;         f(3,5,7) = f(3,5) + f(7) - f(lcm(3,7)) - f(lcm(5,7))
;
; because f(lcm(3,7)) is the sum of numbers which are multiples of
; both 3 and 7, and f(lcm(5,7)) is the sum of numbers divisible by
; both 5 and 7. But this is not yet correct, either. Consider the
; case where the numbers that are summed in f(lcm(3,7)) and
; f(lcm(5,7)) have overlaps. Then those overlap numbers will be
; subtracted out of the sum twice. So it is necessary to add in
; a correction, so:
;
;         f(3,5,7) = f(3,5) + f(7) - f(lcm(3,7)) - f(lcm(5,7))
;                       + f(lcm(lcm(3,7), lcm(5,7)))
;
; But we can simplify this by noticing that
;
;         f(lcm(3,7), lcm(5,7)) = f(lcm(3,7)) + f(lcm(5,7)) - f(lcm(lcm(3,7), lcm(5,7)))
;
; So, we obtain:
;
;         f(3,5,7) = f(3,5) + f(7) - f(lcm(3,7), lcm(5,7))
;
; In general, we have the following recurrence relation:
;
;             f(i) = i * sum-range(floor(n/i))
;           f(i,j) = f(i) + f(j) - f(lcm(i,j))
;         f(i,j,k) = f(i) + f(j,k) - f(lcm(i,j), lcm(i,k))
;       f(i,j,k,l) = f(i) + f(j,k,l) - f(lcm(i,j), lcm(i,k), lcm(i,l))
;
; Running time: constant with respect to n; O(m^2) where m is the
; number of divisors.

(defn gcd [a b]
  (if (zero? b)
    a
    (recur b (mod a b))))

(defn lcm [a b]
  (/ (* a b) (gcd a b)))

(defn sum-range [n]
  (/ (+ (* n n) n) 2))

(defn sum-range-divisors
  ([n x]
     (* x (sum-range (Math/floor (/ n x)))))
  ([n x & xs]
     (let [ys (cons x xs)]
       (- (reduce + (map (partial sum-range-divisors n) ys))
          (sum-range-divisors n (reduce lcm ys))))))

(comment
  
(sum-range-divisors 999 3 5) ;=> 233168.0

)