Problem 46 asks us to find the smallest composite number that can’t be written as a prime number plus twice a square.

My first attempt involved writing compositable? with the for construct. It works, but is inefficient.

(use '[clojure.contrib.lazy-seqs :only (primes)])

(def double-squares (map #(* 2 % %) (range)))

(defn compositable? [n]
  (true? (first (for [a (take-while #(>= n %) primes)
                      b (take-while #(>= (- n a) %) double-squares)
                      :when (= n (+ a b))]
                  true))))

(defn euler-46 []
  (first (remove compositable? (iterate #(+ 2 %) 3))))

(time (euler-46)) ;; "Elapsed time: 2674.650168 msecs"

Why the terrible performance? The for loop foolishly generates all possible combinations instead of just checking for valid combinations.

To check only valid combinations, we need to use our old friend prime?:

(defn prime? [n]
  (and (< 1 n)
       (not-any? #(zero? (rem n %)) (take-while #(<= (* % %) n) primes)))) 

(defn compositable? [n]
  (some #(prime? (- n %)) (take-while #(> n %) double-squares)))

(defn euler-46-revised []
  (first (remove compositable? (remove prime? (iterate #(+ 2 %) 3)))))

(time (euler-46-revised)) ;; "Elapsed time: 47.315354 msecs"

Ahh, that’s better.