First triangle number to have over five hundred divisors

This was another interesting problem at Project Euler (Problem 12). Interesting because the naïve solution to this was all too trivial but slow, which forced me to seek out a better approach and I finally ended up learning something new 🙂

The nth triangle number is defined as the sum of all natural numbers till n. Well, that’s definitely trivial to calculate. It’s basically the sum of first n natural numbers and can be calculated using the well known formula:

n(n+1)/2

So, all that remains is to calculate the divisors and we all know how to do that right? Just count the numbers from 2 to half (or square root, if you prefer) the triangle number that divide the triangle number. So, here’s the code I started with:

// Sum of first n natural numbers
let triangle_number (n:bigint) = (n * (n + 1I)) / 2I ;;

let divisors (n:bigint) =
    let rec divisor_loop (i:bigint) (a_list:bigint list) =
        if (i = 1I) then (i :: a_list)
        else if ((n % i) = 0I) then (divisor_loop (i - 1I) (i :: a_list))
        else (divisor_loop (i - 1I) a_list)
    (divisor_loop (n / 2I) [n;]) ;;

As it turned out, using this method, it takes a really looooong time to even find the divisors of a large number, let alone use it for searching the triangle number with over 500 divisors.

So, I started looking for alternate methods, and finally found one here: http://www.algebra-online.com/positive-integral-divisors-1.htm

The idea is simple actually. Take 5050 for example (the 100th triangle number). It’s prime factors are: 2, 5, 5 and 101. Now reduce the list to a list of unique numbers with their repetition represented in their exponents. So, the list 2, 5, 5, 101 becomes: 2¹, 5², 101¹. Now, add 1 to every exponent and multiply the resulting numbers. So, that would give us: (1+1) * (2 + 1) * (1 + 1) = 12. That’s the number of divisors that 5050 has.

Since I’d already written a function to find the prime factors to solve Problem 3, solving this one was just a matter of writing code to search through a list of triangle numbers to find the first one with more than 500 divisors.