Home > Programming > First triangle number to have over five hundred divisors

First triangle number to have over five hundred divisors

January 28th, 2009 CodeMangler Leave a comment Go to comments

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 <- i + 1I
        done
 
        if( i <= n/2I) then
            factors @ (prime_factors i factors) @ (prime_factors (n / i) factors)
        else
            [] ;;
 
open System.Collections.Generic
 
let prime_factor_map (factors:bigint list) =
    let factor_map = Dictionary<bigint, bigint>()
 
    for factor in factors do
        if (factor_map.ContainsKey(factor)) then
            factor_map.[factor] <- (factor_map.[factor] + 1I)
        else
            factor_map.Add(factor, 1I)
    done
 
    factor_map ;;
 
let number_of_divisors (n:bigint) =
    let factor_map = (prime_factors n []) |> prime_factor_map
    let exponents = factor_map.Values
    let mutable divisor_count = 1I
 
    for exponent in exponents do
        divisor_count <- (divisor_count * (exponent + 1I))
    done
 
    divisor_count ;;
 
let triangle_number_search (minimum_divisor_count:bigint) =
    let mutable keep_searching = true
    let mutable next = 1I
    let mutable n = (triangle_number next)
 
    while keep_searching do
        let divisor_count = (number_of_divisors n)
        if (divisor_count < minimum_divisor_count) then
            next <- next + 1I
            n <- (triangle_number next)
        else
            keep_searching <- false
    done
    n ;;

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# :D )

Categories: Programming Tags: ,
  1. PherricOxide
    March 20th, 2009 at 09:41 | #1
    Reply | Quote

    If you wanted to save a few seconds, you can save on all that multiplication and division when finding the triangle numbers and just make a function that makes use of the last one. This would return the n’th element of the triangle sum sequence when given the n-1 element.

    trinalgenum(int n, int lastterm) {
    return lastterm + n;
    }

    1st term: 1
    2nd term: 1st term + 2
    3rd term: 2nd term + 3… etc.

  2. codemangler
    March 22nd, 2009 at 02:58 | #2
    Reply | Quote

    @PherricOxide
    Thanks for the tip :)

  1. No trackbacks yet.