What is the value of the first triangle number to have over five hundred divisors?
Permalink: http://projecteuler.net/problem=12
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?
When we see infinite sequence of some numbers, first thing that we do is implement it with using lazy sequences. Simple explanation and example for Fibonacci numbers can be found in Clojure Euler: Problem 002.
We have an easy case, so we implement triangle number as sum of all integers below:
(defn triangle-number [n]
(reduce + (range 1 (inc n))))
Don’t miss the possibility reduce complexity from O(n) to O(1).
Just apply arithmetic progression formula.
(defn triangle-number [n]
(* n (/ (+ n 1) 2)))
Okey, we did small optimization (not so small) here and we have a function that calculates
triangle number for n. Let’s find all of them!
(def triangles (map triangle-number (iterate inc 1)))
triangles refers to lazy sequence of triangle numbers.
Do not evaluate lazy seqs!
Use limit functions as take, take-while, drop, drop-while to test the
sequence values, or build other lazy seqs with filter, map, etc.
Now, we need a function to calculate number of divisors.
(defn num-of-divisors [n]
(* 2 (count (filter #(= (mod n %) 0) (range 2 (inc (int (sqrt n))))))))
If we remember Clojure Euler: Problem 003
then we know that using sqrt(n) instead of n as upper bound for divisors
saves much time.
Don’t forget mutiply that value by two, as you skip number after sqrt(n).
Last step: to calculate number over 500 divisors
(first (drop-while #(< (num-of-divisors %) 500) triangles))
We got the result, but spent ~11 secs. Too much.
How can we improve our solution?
There is theorem about Prime Factorization states:
Every positive integer has a unique prime factorization
For example: 15 = 3^1 * 5^1, 18 = 2^1 * 3^2 and so on.
Not hard to see that number of divisors from such factorization can be obtained by multiplying all prime powers incremented by one.
For example number 18 have 6 divisors (1, 2, 3, 6, 9, 18). If we take factorization 18 = 3^1 * 5^1, then number of divisors is equal to (1 + 1) * (2 + 1) = 6. You see, the same. Not hard to prove this theorem or read the proof.
Stop math, we need to code, so let’s code that.
First of all, we need factorization method:
(defn factorize [n]
(loop [x n [p & ps] primes factors []]
(cond (= 1 x) factors
(zero? (mod x p)) (recur (/ x p) primes (conj factors p))
:else (recur x ps factors))))
It uses primes from clojure.contrib.lazy-seqs.
This method prints all factors (including duplicates) for n.
For example:
(factorize 18) => [2 3 3]
But instead of actual values of divisors, we just need their count.
(defn factorize-count [n]
(reduce * (map (comp inc count) (vals (group-by identity (factorize n))))))
Calculate the result again:
(first (drop-while #(< (factorize-count %) 500) triangles))
Bingo! It gives the correct result in less than 3 seconds. Not bad as improvement.
P.S. If you test-addicted person, you, probably, point out
that function num-of-divisors yields incorrect result for input 1.
We can live with that, because our needed number is much greater than 1.