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:

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 (you’ll have to scroll to the end of the page to get to the part where they explain finding the number of divisors for a number)

The idea is simple actually. Take *5050* for example (the *100*th 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 ^{1}, 5^{2},101^{1}*. 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. And, of course, that can be verified using the divisors method:

(divisors 5050I);; -> [1I; 2I; 5I; 10I; 25I; 50I; 101I; 202I; 505I; 1010I; 2525I; 5050I]

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. Here’s the final code I ended up with:

// Sum of first n natural numbers let triangle_number (n:bigint) = (n * (n + 1I)) / 2I ;; let divides (n:bigint) (i:bigint) = n % i = 0I ;; let is_prime (n:bigint) = let rec prime_check_loop (i:bigint) = ( i > (n / 2I) ) || ((not (i |> divides n)) && prime_check_loop (i + 1I)) prime_check_loop 2I ;; let rec prime_factors (n:bigint) (factors:bigint list) = if (is_prime n) then n :: factors else let mutable i:bigint = 2I; while (n % i <> 0I) && (i <= n/2I) do i() for factor in factors do if (factor_map.ContainsKey(factor)) then factor_map.[factor] prime_factor_map let exponents = factor_map.Values let mutable divisor_count = 1I for exponent in exponents do divisor_count |

This took less than a minute to run and running it gives:

(triangle_number_search 500I);; -> 76576500I

So, the first triangle number to have over 500 divisors is: *76576500*

(btw, it has 576 divisors)

(and as you can see, I’m still not very proficient with F# 😀 )