Project Euler Problem 44

Ivar Thorson bio photo By Ivar Thorson

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"