Project Euler in Clojure – Problem 3

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 2 can be found here.

Problem 3 of Project Euler is described as:

What is the largest prime factor of the number 600851475143 ?

For this problem, I needed to generate the prime factors of a number. In order to generate the prime factors, I decided to pul out the Uncle Bob’s (found here, here, here, and here) Prime Factors Kata and apply it to Clojure. By doing this kata, I test drove the result, and decided I would give Brian Marick’s Midje a shot and play with that some as well. The resulting tests are as follows.

(ns project-euler.prime-factors-test
  (:use clojure.test
        midje.sweet
        project-euler.core))

(defn mersenne [n]
  (int (dec (Math/pow 2 n))))

(fact
  (prime-factors-of 1) => []
  (prime-factors-of 2) => [2]
  (prime-factors-of 3) => [3]
  (prime-factors-of 4) => [2 2]
  (prime-factors-of 5) => [5]
  (prime-factors-of 6) => [2 3]
  (prime-factors-of 7) => [7]
  (prime-factors-of 8) => [2 2 2]
  (prime-factors-of 9) => [3 3]
  (prime-factors-of 10) => [2 5]
  (prime-factors-of 11) => [11]
  (prime-factors-of 12) => [2 2 3]
  (prime-factors-of 16) => [2 2 2 2]
  (prime-factors-of 25) => [5 5]
  (prime-factors-of (* 2 3 5 7 11 17 37)) => [2 3 5 7 11 17 37]
  (prime-factors-of (mersenne 17)) => [(mersenne 17)])

The total solution to problem 3 is as follows, with the test driven function for generating the prime factors, is:

(defn factors-starting-at [f n]
  (cond (= n 1) []
        (zero? (rem n f)) (cons f (factors-starting-at f (/ n f)))
        :else (recur (inc f) n)))

(defn prime-factors-of [n]
  (factors-starting-at 2 n))

(defn problem3 []
  (reduce max (prime-factors-of 600851475143)))

The resulting function for prime-factors-of calls the recursive function factors-starting-at with the first factor of 2, and the number itself. The factors-starting-at returns an empty vector when n is one. When the factor is actually a factor of the number (zero? (rem n f)) the returned result is the factor cons’ed onto the result of calling factors-starting-at again with the same factor, and the number divided by that factor. Otherwise, we return the result of recur-ing with the same number and the factor incremented again.

The solution to problem 3 is actually very simple in Clojure after one generates the prime factors for a number. All that one has to do is reduce the sequence of prime factors with the function max to find the largest prime factor for the number 600851475143.

I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Updated**
Here is my approach to Problem 4 in Clojure.

–Proctor

6 thoughts on “Project Euler in Clojure – Problem 3

  1. Pingback: Project Euler in Clojure – Problem 2 « Proctor It

  2. Pingback: Project Euler in Clojure – Problem 4 « Proctor It

  3. kawas

    Hi, nice reading

    Did you consider appling max to the factor collection instead of reduce ?

    Seems to me that you could replace your 2 functions used to search prime factors for 1.
    To me factor-starting-at does not encapsulate a generic behavior that need to be defined on its own.
    A function with loop/recur and an accumulator (for example an hashset) will do the job and you got tail recursion as a bonus 😉

    bye

    Reply
    1. Proctor

      kawas,

      I probably should have made the function factors-starting-at private by declaring it defn-, if my knowledge of Clojure is accurate. It was defined as a method to be able to get the tail call recursion on the :else case of the cond function. I would love to see a snippet of your function using loop/recur to see your approach to using this, as I would guess my approach is still a bit imperative in that sense.

      As for the apply versus reduce call, I have done apply in some of the problems and reduce in others. If there is a good way to determine when to do one or the other I would love to hear that as well.

      Thanks for your comments.
      –Proctor

      Reply
      1. kawas

        Hello,

        To me, because of the 2nd line of factor-starting-at, the function may not be tail recursive.

        The alternative using a loop/recur may look like this:
        (defn prime-factors [n]
        (loop [f 2 n n res []]
        (cond
        (<= n 1) res
        (zero? (rem n f)) (recur f (quot n f) (conj res f))
        :else (recur (inc f) n res))))

        Note1: I've used (<= n 1) because the code fail on double precision arithmetic :
        (prime-factors-of (Math/pow 2 59))

        Note2: Seems like there is a bug using bignums too :
        (prime-factors (bigint (bigdec (Math/pow 2 59))))

        Cheers

        Reply
        1. Proctor

          kawas,

          Thanks for the update. I will have to play with your solution and those possible bugs. I am thinking I will even try again to see if I can’t get the function call in the second conditional (zero? (rem n f)) to use recur, and use what I did and what you gave me to better understand recur at the function level versus using recur in a loop.

          –Proctor

          Reply

Leave a Reply

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