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
Pingback: Project Euler in Clojure – Problem 2 « Proctor It
Pingback: Project Euler in Clojure – Problem 4 « Proctor It
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
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
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
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