Project Euler Problem 47

Ivar Thorson bio photo By Ivar Thorson

Problem 47 is a rather strange computation, because the author of the problem wanted us to bundle together multiples of a prime factor, which I found a little unusual because it means considering a prime number to an exponent as “prime”, which isn’t strictly true. Unfortunately, this additional constraint on the problem meant that rather directly use prime-factors-of from problem 12, the prime factors needed little ‘tweak’ to use the largest multiplicity possible for each prime.

Here is the result of the tweaking:

;; From problem 12
(defn prime-factors-of
  "Returns a sorted list of prime factors of num, including multiplicity."
  (let [q (Math/sqrt num)
        factor? (fn [nom den] (zero? (rem nom den)))] 
    (loop [n num
           d 2
           r []]
       (> d q) (concat r [n]) 
       (= n d) (concat r [n])      
       (factor? n d) (recur (/ n d) d (conj r d)) 
       true          (recur n (inc d) r)))))

(defn tweaked-factors [factors]
  (let [f (frequencies (prime-factors-of factors))]
    (map #(* % (f %)) (keys f))))

(defn euler-47 [n]
  (let [groups (partition n 1 (iterate inc 2))
        myfn (fn [g]
               (let [f (map #(tweaked-factors %) g)]
                 (and (every? #(= n (count %)) f)
                      (distinct? (apply concat f)))))]
    (first (filter myfn groups))))

Incrementally checking the return value of the function turned out to be rather useful for testing correctness:

user> (euler-47 2)
(14 15)
user> (euler-47 3)
(644 645 646)
user> (euler-47 4)
(134043 134044 134045 134046)