## Clojure exercise: calculate perfect numbers

September 18, 2010 at 6:27 pm | Posted in Clojure, Programming | 5 CommentsAccording 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

### Leave a Reply

Create a free website or blog at WordPress.com.

Entries and comments feeds.

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

Comment by pepijndevos— September 19, 2010 #

Nice functional progression towards a first solution.

Another exercise is: make it faster!

😉

Comment by klang— September 19, 2010 #

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].

Comment by maurits— September 19, 2010 #

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

Comment by dpassen1— September 19, 2010 #

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.

Comment by maurits— September 19, 2010 #