Clojure Euler: Problem 023

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

Permalink: http://projecteuler.net/problem=23

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.

mishadoff 10 May 2014
blog comments powered by Disqus