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.

Comments are closed.