# Project Euler Problem 41 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.