Problem 023: Non-abundant Sums

From Project Euler:

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be $1 + 2 + 4 + 7 + 14 = 28$, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

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

This one could potentially be done in a more efficient manner, but it runs reasonably quickly.
We'll first start off with a function that gets all the abundant numbers up to a certain maximum, using

sum-divisors

from our amicable numbers problem:

(defn abundant-numbers
  "Gets all abundant numbers below a maximum."
  [max]
  (set (->> (range 1 max)
            (filter #(< % (sum-divisors %))))))

From there, we'll use a predicate to determine if something is the sum of two abundant numbers:

(defn sum-of-elements?
  "Determines if a number is the sum of two elements in a set."
  [s n]
  (some #(contains? s (- n %)) s))

Combining these two functions, we can put it all together:

(defn not-sum-of-abundants
  [max]
  (let [abundants (abundant-numbers max)]
    (->> (range 1 max)
         (remove #(sum-of-elements? abundants %))
         (reduce +))))

This runs in a reasonable amount of time:

$ lein run
Processing...
Total is: 4179871
"Elapsed time: 4959.157526 msecs"

While 5 seconds isn't really ideal, it is fast enough for our purposes. I did try one alternative method, which was to first compute the abundant numbers, followed by the set of all sums of two abundant numbers, and then filtering one set on the other. This unfortunately took 30 seconds, so I stuck with this method here.