# Project Euler Problem 47

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."
[num]
(let [q (Math/sqrt num)
factor? (fn [nom den] (zero? (rem nom den)))]
(loop [n num
d 2
r []]
(cond
(> 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)

Ciao!