August 13, 2018

## 4clojure 148 - The Big Divide

Write a function which calculates the sum of all natural numbers under n (first argument) which are evenly divisible by at least one of a and b (second and third argument). Numbers a and b are guaranteed to be coprimes.

Note: Some test cases have a very large n, so the most obvious solution will exceed the time limit.

```
(ns live.test
(:require [cljs.test :refer-macros [deftest is run-tests]]))
;; jafingerhut's solution:
;; The trick to calculating the answer very quickly is knowing a few
;; math facts.
;; 1. The sum of all numbers from 1 through n, inclusive, is
;; n*(n+1)/2. See Wikipeda article on Arithmetic Progression for
;; one proof of this (in a more general form).
;; 2. The sum of all numbers that evenly divide a that are less than n
;; is:
;; a + 2*a + 3*a + ... + k*a
;; where k is largest integer such that k*a < n, which is
;; floor((n-1)/a), or (quot (dec n) a). By factoring out a, we can
;; see this is equal to:
;; a * (1 + 2 + 3 + ... + k)
;; By fact 1, this is equal to:
;; a * k * (k+1) / 2
;; 3. Numbers less than n that are evenly divisible by at least one of
;; a and b are:
;; divisible by a: a + 2*a + 3*a + ... + k*a
;; divisible by b: b + 2*b + 3*b + ... + l*b where l=(quot (dec n) b)
;; We can use fact 2 to easily calculate these two sums, but that
;; would double-count all of these numbers:
;; divisible by a*b: a*b + 2*a*b + 3*a*b + ... + m*a*b
;; We know those are the only numbers double-counted, because we
;; are told that a and b are coprime. Fortunately it is easy to
;; calculate that sum and subtract it out.
(defn big-divide [n a b]
(let [sum-multiples-of (fn [divisor]
(let [x (quot (dec n) divisor)]
(/ (*' divisor x (inc x)) 2)))]
(- (+ (sum-multiples-of a) (sum-multiples-of b))
(sum-multiples-of (* a b)))))
(deftest big-divide-test
(is (= 0 (big-divide 3 17 11)))
(is (= 23 (big-divide 10 3 5)))
(is (= 233168 (big-divide 1000 3 5)))
(is (= "2333333316666668" (str (big-divide 100000000 3 5))))
(is (= "110389610389889610389610"
(str (big-divide (* 10000 10000 10000) 7 11))))
(is (= "1277732511922987429116"
(str (big-divide (* 10000 10000 10000) 757 809))))
(is (= "4530161696788274281"
(str (big-divide (* 10000 10000 1000) 1597 3571)))))
(run-tests)
```