Select Page

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 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: 21, 52,1011. 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# 😀 )