Project Euler problem in clojure

[John Holland]

I'm working on problems at projecteuler.net in Clojure.

There is a particular problem that my code doesn't seem to work for. The
problem is:


==================================
The sequence of triangle numbers is generated by adding the natural
numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 =
28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five
divisors.

What is the value of the first triangle number to have over five hundred
divisors?
========================================

I've written the following clojure code to solve it:



(defn triangle [n] (reduce + (range n)))

(defn factors [n] (conj
(filter #(= 0 (mod n %)) (range 1 (+ 1 (/ n 2))))n ))

(defn num-of-factors [n] (count (factors n)))


(def lazytri (lazy-seq (map triangle (range))))

(take 1 (filter #(> (num-of-factors %) 499) lazytri))


with the cutoff of 499, this runs forever as far as I can tell. In fact
it will work up to 100, but not at 200.

The following Java code quickly returns the same answer as the clojure
code for the same cutoffs, and quickly returns the correct answer for
the 499 cutoff.

Why doesn't my clojure code return for these larger values?

=================================================================

public class Triangles {

public static void main(String[] args){
int number = 0;
int i = 1;

while(numberOfDivisors(number) < 500){
number += i;
i++;
System.out.println(number);
}
}
private static int numberOfDivisors(int number){
int nod = 0;
int sqrt = (int) Math.sqrt(number);

for(int i = 1; i<= sqrt; i++){
if(number % i == 0){
nod += 2;
}
}
//Correction if the number is a perfect square
if (sqrt * sqrt == number) {
nod--;
}

return nod;

}

}

[John Holland]

OK, with a coding improvement


(defn factors-sqrt [n]
(filter #(= 0 (mod n %)) (range 1 (+ 1 (Math/sqrt n )))))

(defn num-of-factors [n] (* 2 (count (factors-sqrt n))))

it works for 499. (Idea being factors come in pairs, each factor >
sqrt(x) corresponds to one > sqrt(x))


Was it just running infinitely slow in Clojure relative to Java before??

John

[Meikel Brandmeyer (kotarak)]

Hi,

Am Donnerstag, 20. Juni 2013 15:19:40 UTC+2 schrieb John Holland:

(defn triangle [n] (reduce + (range n)))

(def lazytri (lazy-seq (map triangle (range))))

Some quick idea: here is a major difference in your clojure and your java implementation. You always recompute the whole sum for each step. While you only increase a counter in the java version. A better lazytri implementation would be:

(def lazytri (reductions + (range 1 Long/MAX_VALUE)))

You don't use sqrt in your clojure version? inc is faster than (+ 1 ...). zero? is faster than (= 0 ...).

Kind regards

Meikel

[Alan Malloy]

More importantly than any of these things, he is hanging onto the head of a very, very large sequence with (def lazytri (map triangle (range))). This will lead to serious memory pressure, and perhaps eventually a slowdown as this sequence takes up all the memory in his app and the GC strains to make a tiny bit of room for other temporary objects. Instead of defining it and then immediately using it, he should simply inline its definition into its use, so that the GC is able to free up the bits of it that are no longer in use.