99 Clojure Problems (35-38)

Once again, a lot of the familiar faces from Project Euler show up to give us a hand. And then, in problem 36, we actually go back and use that list encoding work we did earlier in problem 10. Most of my learning moments this set were in problem 38, where I struggled a little to abstract the timing harness enough. Defining my own operator was cool too, but not as fancy looking as scala, ruby, or python.

; P35 (**) Determine the prime factors of a given positive integer.
(comment "Construct a flat list containing the prime factors in ascending order.")
(defn prime-factors [n]
  (loop [number n
         curr 2
         output '()]
    (cond 
      (= 1 number) (reverse output)
      (evenly-divisible number curr) (recur (/ number curr) curr (conj output curr))
      :else (recur number (inc curr) output))))

; P36 (**) Determine the prime factors of a given positive integer (2).
(comment "Construct a list containing the prime factors and their multiplicity.") 
(defn prime-factors-mult [n] (encode (prime-factors n)))

; stolen from http://rosettacode.org/wiki/Exponentiation_operator#Clojure
(defn ** [x n] (if (zero? n) 1 (reduce * (repeat n x))))

; P37 (**) Calculate Euler's totient function phi(m) (improved).
(comment "See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m>) can be efficiently calculated as follows: Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:") 
(defn totient2 [n] 
  (let [pfs (prime-factors-mult n)]
    (reduce * (map (fn [[m p]] (* (dec p) (** p (dec m)))) pfs))))

; P38 (*) Compare the two methods of calculating Euler's totient function.
(comment "Use the solutions of problems P34 and P37 to compare the algorithms. Try to calculate phi(10090) as an example.")
(defn timer [which function n]
  (let [start (System/currentTimeMillis)
        answer (function n)
        end (- (System/currentTimeMillis) start)]
  (println which "{" answer "} takes" end "ms")))

(defn benchmark [n] 
  (doseq [i (range 1 11)]
	  (println "Run" i)
	  (timer "p34" totient n)
	  (timer "p37" totient2 n)
	  (println "------\n")))

(benchmark 10090)