Project Euler Problem 41

Ivar Thorson bio photo By Ivar Thorson

Problem 41 is yet another variation on the theme of pandigitality and primality. If nothing else, it is teaching me how to reuse my own code…

;; from euler-32
(defn all-unique? [digits]
  (let [unique (distinct digits)]
    (= (count unique) (count digits))))

(defn n-pandigital? [n digits]
  (and (nil? (some zero? digits))
       (nil? (some #(< n %) digits))
       (= n (count digits))
       (all-unique? digits)))

;; as-digits is from euler-30
(defn pandigital-prime? [pr]
  (let [d (as-digits pr)]
    (n-pandigital? (count d) d)))

(defn euler-41 []
  (last (filter pandigital-prime?
                (take-while #(< % 1000000)
                            (drop-while #(< % 100000) primes)))))
(time (euler-41)) ;;  "Elapsed time: 9591.044968 msecs"

Hmm, performance isn’t bad, especially when the primes are already cached into memory; the speed improves by about 3x. However, we also could try an algorithm that tests for primality instead of pandigitality:

(use '[clojure.contrib.combinatorics :only (permutations)])

;; Use prime? and as-int from problem euler-37
(defn euler-41-alt
  ([] (euler-41-alt "987654321"))
  ([s] (first (filter #(prime? (as-int %))
                      (lazy-cat (permutations s)
                                [(euler-41-alt (rest s))])))))

(time (euler-41-alt)) ;; "Elapsed time: 1866.518849 msecs"

I guess it’s cheaper to check generate pandigital permutations and check primality than to generate primes and check pandigitality.