This was challenging! Problem 60 asks us to find the sum of five primes, any pair of which must – when concatenated in any order – form another prime.

If you assume (incorrectly) that finding concatenatable primes in order will bring about the minimum sum, you may write (broken) code that looks like this:

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

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

(defn all-pairs-prime?
  "Returns true iff p forms only prime numbers when concatenated with elements is coll."
  [coll p]
  (let [pairs (mapcat (fn [a b] [[a b] [b a]]) coll (repeat p))
        nums (map (fn [[a b]] (bigint (apply str (concat (str a) (str b))))) pairs)]
    (every? prime? nums)))

(def concatenatable-primes
     (iterate (fn [c]
                (conj c (first
                         (filter #(all-pairs-prime? c %)
                                 (drop-while #(< % (apply max c)) primes)))))
              [3]))

(take 4 concatenatable-primes) ;; ([3] [3 7] [3 7 109] [3 7 109 673])

(take 5 concatenatable-primes) ;; ka-BOOOM! Doesn't seem to ever finish.

After wasting an embarrassingly long amount of time trying to figure out why this was either incorrect (or why the performance was so terrible that it wasn’t computing the answer in a reasonable amount of time), I sat back and rethought my assumptions, and tried an algorithm that would try more possibilities.

But before we get to that algorithm, let’s improve that awful all-pairs-prime? a little because we will certainly need to use it again.

(defn all-pairs-prime?
  "Returns true iff p forms only prime numbers when concatenated in any order
  with an element of coll."
  [coll p]
  (every? prime? (interleave (map #(bigint (str p %)) coll)
                             (map #(bigint (str % p)) coll))))

Ahh, that’s much more concise and to the point. But wait: could performance be improved if avoid the integers->strings->bigint type conversion? As it turns out, this next version use logarithms to find the number of digits in each number, and as a result goes about twice as fast as the above:

(use '[clojure.contrib.math :only (expt)])

(defn x10 [n] (expt 10 (inc (quot (Math/log n) (Math/log 10)))))

(defn all-pairs-prime?
  "Returns true iff p forms only prime numbers when concatenated in any order
  with an element of coll."
  [coll p]
  (every? prime? (interleave (map #(+ % (* p (x10 %))) coll)
                             (map #(+ p (* % (x10 p))) coll))))

Now let’s correct the core algorithm of this problem. Rather than assume that the solution for five concatenatable primes will use the smallest four concatenatable primes plus one more prime, let’s go back to building a list of five primes from scratch. That is, we will start with a list of prime numbers, build up pairs of concatenatable primes in this list, then triplets, then quadruplets, and finally groups of five. Returning the first of these should give the correct answer.

For performance reasons, we want the starting list of candidate prime numbers to be as small as possible and yet still contain all five concatenatable prime numbers. I didn’t see any obvious hints, so I first just guessed that the first five primes were under 1000. This didn’t work, but when I tried 10,000 then the following code solved the problem.

(defn euler-60 []
  (let [ps (take-while #(< % 10000) primes)]
    (first
     (for [a ps
           b (filter #(all-pairs-prime? [a] %) (drop-while #(<= % a) ps))
           c (filter #(all-pairs-prime? [a b] %) (drop-while #(<= % b) ps))
           d (filter #(all-pairs-prime? [a b c] %) (drop-while #(<= % c) ps))
           e (filter #(all-pairs-prime? [a b c d] %) (drop-while #(<= % d) ps))]
       (+ a b c d e)))))

(time (euler-60)) ;; "Elapsed time: 16474.689447 msecs"

The somewhat slow performance of this leaves something to be desired, but this solution seems easy to understand, is concise, and gives the correct answer. Suggestions on a better algorithm are welcome.