Clojure exercise: calculate perfect numbers

September 18, 2010 at 6:27 pm | Posted in Clojure, Programming | 5 Comments

According to Wikipedia a perfect number is a positive integer that is the the sum of the positive divisors excluding the number itself. The first perfect number is 6, because 1, 2, and 3 are its proper positive divisors, and 1 + 2 + 3 = 6. Lets write some code that calculates these perfect numbers in Clojure. I will show this code top-down.

First we’ll start with printing the first 4 numbers. I limit this to 4, because the fifth perfect number (33550336) is already pretty big and will take quite some time to calculate. In Clojure this code looks like this:

(println (take 4 (perfect-numbers)))

No surprises here. We have a function called perfect-numbers which is supposed to return a lazy sequence of this numbers. So lets define this function:

(defn perfect-numbers []
 (filter perfect? (nnext (range)))

Line 1 defines the function perfect-numbers which has no parameters, hence the []. In line 2 we see the (nnext (range)). nnext is not a typo, but is just a shortcut for (next (next …)). So it skips the first two values of the sequence that is returned by (range) which is  zero to infinity. Our range thus starts with 2, because 0 and 1 are no perfect numbers. We filter the perfect numbers from this range by applying the perfect? predicate. In Clojure the question mark is used to indicate that a function returns a boolean.

The perfect? function is defined as follows:

(defn perfect? [n]
 (= n (sum (divisors n))))

As you can see this code corresponds directly to the definition of a perfect number. We have introduced to new functions here: divisors and sum. Lets start with the latter:

(defn sum [s]
 (reduce + s))

Nice, isn’t it? The function sum takes a sequence s as parameter and uses Clojure‘s reduce function to calculate the sum of that sequence. reduce takes two parameters. The first is a function of two arguments. reduce applies this function on the first two elements in a sequence (the second parameter), then applies this function to the result and the third element, and so on. In the above code the function is the add operation (+), and the sequence is s.

And finally the divisors function:

(defn divisors [n]
 (filter #(= (rem n %) 0) (range 1 (inc (/ n 2 )))))

Again no real surprises. The function filters the numbers in the range [1..n/2] with an anonymous function “#(= (rem n %) 0)” that just checks if the remainder of the number and the element in that range (passed as an anonymous parameter %) is zero.

That’s it! Finally all the code together:

(defn divisors [n]
 (filter #(= (rem n %) 0) (range 1 (inc (/ n 2 )))))

(defn sum [s]
 (reduce + s))

(defn perfect? [n]
 (= n (sum (divisors n))))

(defn perfect-numbers []
 (filter perfect? (nnext (range))))

(time (println (take 4 (perfect-numbers))))

What you have seen is very typical for Clojure (and functional programming in general): small well defined functions. If you really want you can combine all those little functions into a single one. I tried this just to check if all the code would fit in a single tweet. It did, easily. If you try this with the above code, you will run into the limitation that you can’t have nested anonymous functions (defined with #), but this can easily be solved by using fn. I’ll leave that as an exercise to the reader.

5 Comments »

RSS feed for comments on this post. TrackBack URI

  1. Nice! Might be even nicer to get this into clojure.contrib.lazy-seqs, together with the fibonacci and prime seqs.

  2. Nice functional progression towards a first solution.

    Another exercise is: make it faster!
    😉

    • I very well realize that the solution I have chosen is pretty naive and thus not very fast. The whole point was to show my readers the beauty of functional programming and Clojure in particular.

      Probably the first step to make it faster is to look at Mersenne Primes, instead of the range [2 .. infinity].

  3. Shouldn’t you only go up to the square root of n, rather than n/2?

    • I could do that, but that would also mean that I would have to generate 2 numbers at a time. For example, when testing if 28 is a perfect number, once I encounter the number 2, which is a divisor, it should also add 14 to the set. This will make the code faster, but also a bit less easy to understand. For real speed improvements I would first look at a completely different algorithm, like one based on Mersenne Primes.


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

Create a free website or blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: