99 Clojure Problems (31-34)

I wanted to complete problems 27 and 28, but it just wasn’t working out. I’ll come back to them later, but for now, here’s numbers 31 through 34.

Since I’m working through Project Euler as a sort of algorithmic kata to stretch my legs in new languages, these prime based problems were a snap.

; A utility method that helps keep things readable.
(defn evenly-divisible [n d] (zero? (mod n d)))

; P31 (**) Determine whether a given integer number is prime.
(defn prime? [n] 
  (loop 1 
    (if (> (* c c) n) 
      true 
      (if (evenly-divisible n c)
        false
        (recur (inc c))))))

; P32 (**) Determine the greatest common divisor of two positive integer numbers.
(comment "Use Euclid's algorithm.")
; my first attempt...
(defn gcd_a [n k] 
  (loop [a (if (< n k) n k)
         b (if (< n k) k n)
         c 2
         o 1] 
    (cond 
      (< a c) o
      (and (evenly-divisible a c) (evenly-divisible b c)) (recur (/ a c) (/ b c) c (* o c))
      :else (recur a b (inc c) o))))

(comment "using euclid's algorithm, which I thought I knew, but I was apparently misremembering")
(defn gcd [m n] 
  (if (zero? n) 
    m 
    (recur n (mod m n))))

; P33 (*) Determine whether two positive integer numbers are coprime.
(comment "Two numbers are coprime if their greatest common divisor equals 1.")
(defn coprime? [n k] (= 1 (gcd n k)))

; P34 (**) Calculate Euler's totient function phi(m).
(comment "Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r <= m) that are coprime to m.") 
(defn totient [n] 
  (count 
    (filter 
      (fn [e] (coprime? e n)) 
      (range 1 n))))

Not only was Project Euler helpful, the fact that these solutions so nicely build upon each other helped speed these through. I think I made the right choice skipping 27-28. The forward momentum has rekindled my interest in learning more about clojure.

4 thoughts on “99 Clojure Problems (31-34)”

  1. in your last one partial would be a handy function to know. it takes a function and some of its args and returns a new function that needs less args than the original.

    (defn totient [n]
          (count
            (filter
              (partial coprime? n)
                (range 1 n))))

    `(partial coprime? n)` returns a function that takes one argument, which is perfect for filter.

    also, i had to look it up and was surprised that clojure has both (mod) and (rem) functions. i’ve always used rem.

  2. Thanks for posting these. If you are working through Project Euler as well, allow me to mention my solutions for the first 25 at http://clojure.roboloco.net. I’m also working through my first steps of this kind of Clojure kata, and if you have better solutions I would love to be corrected.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>