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 '()]
      (= 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)

2 thoughts on “99 Clojure Problems (35-38)”

  1. At this point, Jon, you’re way ahead of me on the Euler Problems. I really want to have a look at your Clojure solutions but I can’t bare to have the solutions uncovered before I take a crack at the problems myself. Slow down, Dude! :)

  2. Hi Jon, I found your `benchmark` function quite helpful. But strangely, while the problem mentions that p37 is an improvement over p34, p34 is running faster on my machine! For eg. p34 takes about 20-30ms whereas p37 takes 430-440ms. Can you please share what kind of timings you were/are getting?


Leave a Reply

Your email address will not be published. Required fields are marked *