I've just noticed that this answer is anticipated by @Nakiya's comments on @Carciginate's answer. I'll leave it up, since it explains things more fully and does go a little further.
There is a single change that makes your algorithm run about twenty times faster, dropping the time taken from about thirty seconds to between one and two seconds.
Look at your is-sum-of-two-abundants?
function:
(defn is-sum-of-two-abundants? [num]
(let [sub-ab (->> abundants
(filterv #(< % num))
(set))]
(some (fn [ab]
(sub-ab (- num ab)))
sub-ab)))
You build a new sub-ab
set every time. And you scan the whole of the abundants
set to do so. You do this for every number you test. So the time this takes is of the order of (* LIMIT (count abundants))
, where ...
(def LIMIT 28123)
Let's construct the abundants
as a sequence, and - from that - as a set:
(def abundants-seq
(->> (range 12 LIMIT)
(map #(vector % (sum-div %)))
(filter #(> (second %) (first %)))
(map first)))
(def abundants-set (set abundants-seq))
- We can use the whole
abundants-set
, created once and for all, to
test for the presence of any one of them. This takes more or less constant
time, regardless of how big the set is.
- Since the
abundants-seq
is in increasing order, we can just stop
when the numbers get too big.
This gives us
(defn is-sum-of-two-abundants? [num]
(let [sub-ab (take-while #(< % num) abundants-seq)]
(some (fn [ab]
(abundants-set (- num ab)))
sub-ab)))
I've kept the name sub-ab
for the candidates, as a sequence, not a set.
So that we can time it, I've made the final calculation into a function:
(defn answer []
(->> (range (inc LIMIT))
(remove is-sum-of-two-abundants?)
(reduce +)))
... taking the chance to elide (filter (complement ... ) ...
into (remove ... ...
.
Timings
Before
user=> (time (let [x (answer)] (println x)))
4179871
"Elapsed time: 29488.662721 msecs"
After
user=> (time (let [x (answer)] (println x)))
4179871
"Elapsed time: 1646.560626 msecs"
The work of constructing abundants-seq
and abundants-set
is done at compile/load time. The former can be done far faster too, as this related discussion describes. However, this is not the dominant phase here.