What is the value of the first triangle number to have over five hundred divisors?

Also known as Project Euler Problem 12.

This is the first one that has proved to be a bit of a challenge for me, and one that forced me both to do a bit of research and to take a look at the efficiency of some of my functions.

First the problem:

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?

Obviously a brute-force approach is not going to work in this case. Since I already had a function for generating prime factors, which I developed for Problem 3, I started thinking about whether it was possible to calculate the total number of divisors of a number based on its prime factors.

It turns out that it is.

The factorisation of a number can be expressed as: P1^F1 * P2^F2 * … * Pn^Fn

And the total number of divisors is: (F1 +1) * (F2 + 1) * … * (Fn + 1)

For example, 28 can be expressed as 2^2 * 7^1 so the total number of divisors is (2 + 1) * (1 + 1) = 6

Or, 36 = 2^2 * 3^2 so the total number of divisors is 3*3 = 9.

Coding this formula was pretty straightforward. Unfortunately, the resulting program ground to a halt once I started looking for more than 200 divisors – and this has had me stumped for a couple of days. I knew my reasoning was sound and I could see the program generating correct results for small numbers of divisors, but I could not figure out why it didn’t scale.

It wasn’t until I went back to look at the efficiency of my factorisation function that the following insight hit me: You don’t need to test whether a number is prime if you can guarantee that your loop will only look at prime mumbers.

This insight resulted in the following, much more efficient, function:

def Factorise(integer):
	factors=[]
	index = 2
	while integer > 1:
		if integer % index == 0:
			factors.append(index)
			integer=integer/index
		else:
			index += 1
	return factors

Starting with an index of 2 (the lowest prime) I simply divide the integer by the index until I get a non integer result. Then I increment the index and start again.

Because the function repeatedly divides out each factor, integer/index can only return an integer result if index is prime.

With this approach, I was able to solve the problem in about half a second.

2 thoughts on “What is the value of the first triangle number to have over five hundred divisors?

  1. #include
    #include
    #include
    void main()
    {
    long int i=1,n,t,sum=0,counter=0;
    clrscr();
    printf(“ntriangle nos are:”);
    while(counter<=500)
    {
    counter=0;
    sum+=i;
    i++;
    printf("nthe no is:");
    printf("%d",sum);
    printf("nfactors of no %d are:",sum);
    for(t=1;t<=sum;t++)
    {
    if(sum%t==0)
    {
    counter++;
    printf("n%d",t);
    }

    }
    }
    printf("nthe no is: %d",i);
    getch();

    }

    Like

  2. Hi santosh

    I’m no C programmer but that looks like it’s going to slow down a lot when you get into high numbers of divisors. Have you run this and, if so, how long did it take?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s