Project Euler Clojure Problem 003

13 Jan

After discovering Project Euler Clojure in my previous post I took a stab at problem 003 – “Find the largest prime factor of the composite number 600851475143”. In the spirit of true learning I did not look at any posted solutions while writing mine.

The first bright idea was to use lazy sequence primes from clojure.contrib.lazy-seqs in reverse order and simply working down divide target number by decreasing prime number looking for zero remainder. Well, it turns out that since primes is infinite simple filtering doesn’t work. Below enters infinite loop and should eventually run out of memory, I think. I just killed the process.

user=> (use '[clojure.contrib.lazy-seqs :only (primes)])
user=> (filter #(= 0 (rem 600851475143 %)) primes)
; never came back...

After pondering some time I decided to abandon “primes in reverse order approach”. If I can not realize infinite lazy sequence, I can look for specific item using nth. Fast forward some time and here is the final solution.

 1 (use '[clojure.contrib.lazy-seqs :only (primes)])
 3 (defn max-fctr [target]
 4   (loop [nbr target, idx 0, fctrs []]
 5     (let [cp (nth primes idx), rmndr (rem nbr cp)]
 6       (if (= 0 rmndr)
 7           (recur (/ nbr cp) 0 (conj fctrs cp))
 8         (if (> cp nbr)
 9           (last fctrs)
10           (recur nbr (inc idx) fctrs))))))
11 (max-fctr 600851475143)

On line 3 I setup explicit recursion point. On line 5 I capture current prime (cp) from primes and compute reminder (rmndr). If reminder is zero we set target number to a larger factor as an optimization, reset primes index to zero and add smaller factor to an accumulating vector of primes. Otherwise, to terminate recursion we compare current prime to our target number and if it is greater return last found factor. If current prime is less, we recur with incremented index. On my laptop above runs in about 20 msecs.

Well it is time to check how above compares to other solutions at project euler’s site… Overall, not bad – my solution is on a shorter side and only the 2nd one that takes advantage of lazy primes. Please note that I did not compare performance of other solutions. The best solution IMHO is by mtgred followed by davirus which looses because it relies on external functions (eg. prime?). Interestingly the best solution has approach similar to mine and both shorter and faster (runs in about 800 microseconds on my laptop). Let me reproduce it here (I made it slightly more readable).

(defn prime-factors [n]
  (let [(some #(if (= 0 (rem n %)) %) primes)]
    (if (= f n) 
      (conj (prime-factors (/ n f)) f))))
(apply max (prime-factors 600851475143)

mtgred uses clever trick with implicit recursion which dispenses with loop/recur and accumulating vector of factors. Also, using some instead of nth eliminates need for index and, my guess, makes it faster. Since unordered set is used #{f} it requires (apply max …).


One Response to “Project Euler Clojure Problem 003”

  1. R. P. Dillon April 11, 2011 at 10:56 #

    Nice to see others doing Project Euler in Clojure! I found it to be a good way to explore the language. Back around the 1.0 days, I put together a slightly different approach. I pushed it to a gist over on Github:

    The basic idea is that we can generate primes completely in advance because we know the stopping criteria, which we capture in a stop predicate passed to a primes generator. Once that machinery is in place, it’s easy to write a prime-factor method that walks the list of primes and tests to see if they’re a factor of a given number. We run that tail-recursively and accumulate the list of factors.

    Clojure’s nice for this problem and problem 8 because it has really nice support for large numbers.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: