This is my solution to Problem 12 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 12 of Project Euler is described as:

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.
[...]
What is the value of the first triangle number to have over five hundred divisors?

And my solution for this, including previously defined functions created as part of solving the previous problems, is the following:

(defn factors-starting-at [f n]
(cond (= n 1) []
(factor-of? f n) (cons f (factors-starting-at f (/ n f)))
:else (recur (inc f) n)))
(defn prime-factors-of [n]
(factors-starting-at 2 n))
(defn factors-count [n]
(multiply (map #(inc %) (vals (frequencies (prime-factors-of n))))))
(defn triangle-numbers
([] (concat [1] (triangle-numbers 1 2)))
([s n] (let [t (+ s n)]
(lazy-seq
(cons t (triangle-numbers t (inc n)))))))
(defn problem12 []
(first (drop-while #(<= (factors-count %) 500) (triangle-numbers))))

The functions `factors-starting-at`

and `prime-factors-of`

get the prime factors of a given number. The function `factors-count`

calls `frequencies`

on the sequence returned by `prime-factors-of`

, and then increments each item in the sequence and multiplies the items together, to get the total number of factors for a number. I found this formula for getting the count of the factors from StackOverflow question: Algorithm to calculate the number of divisors of a given number.

The function `triangle-numbers`

gets a lazy sequence of the triangle numbers, by taking the previous triangle number, and adding the index of the current triangle number.

The function `problem12`

then drops the items in the sequence while the result of `factors-count`

is <= 500, and gets the first triangle number, which is the first number with a the count of the number of factors greater than 500.

–Proctor

### Like this:

Like Loading...

*Related*

#1 by Arcane Sentiment on July 16, 2012 - 15:24

`triangle-numbers`

can be written without explicit recursion — see`reductions`

. (Explicit recursion on lists is usually a mistake.) Or you can calculate the nth triangular number directly: (defn triangle [n] (* n (inc n) 1/2)).Why compute the number of divisors from the prime factors when you can just count them by brute-force divisibility testing?

#2 by Proctor on July 16, 2012 - 16:09

I am going to have to remember

`reductions`

, that seems like it will be very handy.As far as the brute forcing of the factors, if I recall correctly, the result was taking much longer than I was wanting, being more than a few seconds, since I was doing a pure brute force calculation

`(count (filter #(factor? % n)) (range 1 (inc n)))`

, so I went looking for a formula that would decrease the amount of time it was taking to solve the problem.