Problem 44 asks us to find the smallest distance between two pentagonal numbers that produce another pentagonal number when added to or subtracted from each other.

A for loop seemed to be the right idiom to quickly generate and then filter down to valid pentagonal combinations:

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

(def pentagonal-nums
     (map (fn [n] (* (/ 1 2) n (- (* 3 n) 1))) (iterate inc 1)))

(defn natural? [n] (= n (int n))) 

(defn pentagonal? [n]
  (let [m (/ (+ 1 (Math/sqrt (+ 1 (* 24 n)))) 6)]
    (and (> n 0) (natural? m))))

(defn euler-44 []
  (first (for [a pentagonal-nums
               b (take-while #(> a %) pentagonal-nums)
               :when (pentagonal? (+ a b))
               :when (pentagonal? (abs (- a b)))]
           (abs (- a b)))))

Looking at the solution posted on clojure-euler, I noticed that somebody named “kcafka” defined his infinite sequence of pentagonal numbers as:

    (def pents
      (map #(bit-shift-right (* % (dec (* 3 %))) 1) (iterate inc 1)))

Strangely (to me at least), it’s about 10 times faster than my definition:

user> (time (reduce + (take 100000 pentagonal-nums)))
"Elapsed time: 940.094702 msecs"
500005000000000
user> (time (reduce + (take 100000 pents)))
"Elapsed time: 94.981341 msecs"
500005000000000

Can you guess why? My theory is that using the bitshift avoids a type conversion to and from the ratio type created by the (/ 1 2) expression in the original definition. Let’s check that:

(def pentagonal-nums
     (map (fn [n] (* (/ 1 2) n (- (* 3 n) 1))) (iterate inc 1)))

(def pentagonal-nums-div
     (map (fn [n] (/ (* n (- (* 3 n) 1)) 2)) (iterate inc 1)))

        
user> (time (reduce + (take 100000 pentagonal-nums)))

"Elapsed time: 992.529968 msecs"
500005000000000
user> (time (reduce + (take 100000 pentagonal-nums-div)))

"Elapsed time: 97.825708 msecs"
500005000000000
user> (type (/ 1 2))
clojure.lang.Ratio

Looks like I was right!

In conclusion, if we redefine pentagonal-nums to avoid that ratio type conversion and slightly improve pentagonal?, we get the following succinct and efficient solution:

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

(def pentagonal-nums
     (map (fn [n] (/ (* n (- (* 3 n) 1)) 2)) (iterate inc 1)))

(defn pentagonal? [n]
  (zero? (rem (+ 1 (Math/sqrt (+ 1 (* 24 n)))) 6)))

(defn euler-44 []
  (first (for [a pentagonal-nums
               b (take-while #(> a %) pentagonal-nums)
               :when (pentagonal? (+ a b))
               :when (pentagonal? (abs (- a b)))]
           (abs (- a b)))))

(time (euler-44)) ;; "Elapsed time: 1193.450608 msecs"