# Project Euler in Clojure – Problem 12

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

## 2 thoughts on “Project Euler in Clojure – Problem 12”

1. Arcane Sentiment

`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?

1. Proctor

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.