After a long and wonderful three week vacation (and another week of just getting back into the flow), it’s time to return to the daily little bit of practice to stay sharp. Let’s get started!

Problem 69 wasn’t a programming problem at all, it was a math problem. One could solve it with a few minutes of logic, a pencil, and paper.

The key insight is that multiplying small primes together will result in products with the fewest number of relative primes. Because a small phi will maximize n/phi(n), our answer is in fact simply the product of the first few primes.

(use '[clojure.contrib.lazy-seqs :only (primes)])

(defn euler-69 []
  (last (take-while #(< % 1e6) (reductions * primes))))

(time (euler-69)) ;; "Elapsed time: 0.263869 msecs"

I really was pleased when I realized how reductions made this code a one-liner. Problem solved!

Although not really necessary, if you need some help or insight into the totient function, you might enjoy playing with these functions, as I did.

(defn coprime? [p q]
  {:pre [(< 0 p) (< 0 q)]}
  (not-any? #(and (zero? (rem p %))
                  (zero? (rem q %)))
            (take-while #(<= (* 2 %) p) primes)))

(defn brute-totient [n]
  (count (filter #(coprime? n %) (range 1 n))))

Of course, it’s much wiser to use an analytic equation for the totient of larger numbers (read up on Euler Products):

;; Prime-factors-of 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 unique-prime-factors-of [n]
  (vec (into #{} (prime-factors-of n))))

(defn euler-totient [n]
  (* n (reduce * (map #(- 1 (/ 1 %)) (unique-prime-factors-of n)))))

Ciao for today!