In number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself (also known as its aliquot sum). Equivalently, a perfect number is a number that is half the sum of all of its positive divisors (including itself) i.e. σ1(n) = 2n.
After watching a Functional Thinking talk by Neal Ford, needed to give it some clojure…
(ns perfect-numbers.core) (defn is-factor? [divident divisor] (zero? (mod divident divisor))) (defn factors [number] (distinct ; no dups for perfect squares (e.g. 16, 64, 49) (mapcat #(when (is-factor? number %) ; when a factor is found [(/ number %) %]) ; return a pair of [number/factor, factor] (range 1 (inc (Math/sqrt number)) 1)))) ; go upto a (sqrt number) inclusively (defn perfect? [number] (= (reduce + (factors number)) (* 2 number))) ; check if sum of factors = 2*N (def perfect-numbers (filter perfect? (nnext (range)))) |
Let’s give it a spin:
$ lein repl REPL started; server listening on localhost port 61776 user=> (use 'perfect-numbers.core) nil user=> (take 4 perfect-numbers) (6 28 496 8128) user=> |
Let’s time it:
user=> (time (doall (take 4 perfect-numbers))) (6 28 496 8128) "Elapsed time: 0.123 msecs" user=> user=> (time (doall (take 5 perfect-numbers))) (6 28 496 8128 33550336) "Elapsed time: 1.8967263496E7 msecs" ( 5 hours 16 minutes ) |
I did a Ruby one for giggles. Took 17 seconds. LOL. Of course, I made no attempt at optimizing. Just brute-forced it.
https://gist.github.com/3961422
Here’s another version that’s optimized. Uses the square root trick to avoid the brute force. The run-time was 0.5 seconds. https://gist.github.com/3961738
I need to change (take 4 (perfect-numbers)) to (take 4 perfect-numbers) to make it work, otherwise I will see this error: java.lang.ClassCastException: clojure.lang.LazySeq cannot be cast to clojure.lang.IFn (NO_SOURCE_FILE:0)
Do you know why it happens?
I am new to Clojure
@Russel,
You are right by omitting the parentheses around “perfect-numbers”. The reason you are getting an exception, is because “perfect-numbers” is, in fact, a lazy sequence (e.g. not a function):
By if “perfect-numbers” is in parentheses, Clojure tries to call it as a function, and complains that it cannot do that, since a “clojure.lang.LazySeq cannot be cast to clojure.lang.IFn”.
/Toly