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

#1 by kawas on May 31, 2012 - 07:16

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

#2 by Proctor on May 31, 2012 - 15:59

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

#3 by kawas on June 1, 2012 - 09:56

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

#4 by Proctor on June 1, 2012 - 10:06

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