Project Euler Problem 50

Ivar Thorson bio photo By Ivar Thorson

Finally, we made it to the 50th problem! In fact, if this were an old-school Japanese RPG, I’m pretty sure we would be hearing some victory music playing about now…

For this problem, we just need to find the sum of the longest sequence of consecutive primes that sums to a prime less than 1,000,000.

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

;; This is better than euler-19 accum, which wasn't lazy
(defn make-seq-accumulator [seq]
  (map first (iterate (fn [[sum s]]
                        [(+ sum (first s)) (next s)])
                      [(first seq) (rest seq)])))

(def prime-sums (conj (make-seq-accumulator primes) 0))

(defn euler-50 [goal]
  (loop [c 1]
    (let [bots (reverse (take c prime-sums))
          tops (take c (reverse (take-while #(> goal (- % (last bots)))
                                            (rest prime-sums))))]
      (if-let [v (some #(if (prime? %) % nil)
                       (map #(- %1 %2) tops bots))]
        (recur (inc c))))))

(euler-50 1000000) ;; "Elapsed time: 2.675548 msecs"

That may be my most performant solution yet, especially for my first trial! (To be honest, I’m pretty sure primes must already be cached in memory…)

See you later!