# Clojure Euler: Problem 023

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

To define abundant number let’s revisit `sum-of-proper-divisors` from the Clojure Euler: Problem 021

``````(defn sum-of-proper-divisors [n]
(let [base (filter #(zero? (mod n %)) (range 2 (Math/sqrt n)))]
(reduce + 1 (concat (map #(/ n %) base) base))))
``````

Using that function, `abundant?` predicate just follows definition.

``````(defn abundant? [n]
(> (sum-of-proper-divisors n) n))
``````

If you look carefully at `sum-of-proper-divisors` it is buggy.

``````(sum-of-proper-divisors 25) => 1 ;; instead of 6
``````

Square numbers are not handled correctly. To fix that we add one more list to `concat`.

``````(defn sum-of-proper-divisors [n]
(let [divs (filter #(zero? (mod n %)) (range 2 (Math/sqrt n)))]
(reduce + 1 (set (concat
(let [isq (int (Math/sqrt n))]      ;; added
(if (= n (* isq isq)) [isq] []))  ;; added
divs
(map #(/ n %) divs))))))
``````

Double check

``````(sum-of-proper-divisors 25) => 6
``````

Great! Next step is to find all integer numbers which can not be written as the sum of two abundant numbers.

Precalculate all abundant numbers:

``````(def abundant (filter abundant? (range 12 28124)))
``````

Now we can build all numbers which can be written as two abundant numbers and find their sum.

``````(->> (for [i abundant j abundant
:let [num (+ i j)]
:when (< num 28124)]
num)
(distinct)
(reduce +)
(- (reduce + (range 1 28124))))
``````

This solution works ~44 sec, too much.

More clever approach is to iterate from all integers upto 28124 and check if some number can be written as a sum of two abundant numbers.

The trick is simple: we building sorted set of abundant numbers

``````(def abundant (into (sorted-set) (filter abundant? (range 12 28124))))
``````

For every integer number `n` we subtract one abundant number and check if `abundant` set contains result. There is a good function some that makes our life easier.

``````(defn abundant-sum? [n abundant]
(some #(abundant (- n %)) abundant))
``````

Finding the sum

``````(->> (range 1 28124)
(remove #(abundant-sum? % abundant))
(reduce +))
``````

It works ~26 sec.

Another optimization is to limit number of abundants in `abundant-sum` function.

``````(defn abundant-sum? [n abundant]
(some #(abundant (- n %))
(take-while #(< % n) abundant)))
``````

Time reduced to ~14 sec. Pretty good.

Code

P.S. Buggy version of `sum-of-proper-divisor` solved the previous problem correctly, but it was just a luck. Make sure you test your functions.

10 May 2014