Home > Programming, Technology > What is the value of the first triangle number to have over five hundred divisors?

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


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.

Here I’m not finding the divisors of all the numbers instead, using the formula

if your number n = a^x * b^y * c^z (where a, b, and c are n’s prime divisors and x, y, and z are the number of times that divisor is repeated) then the total count for all of the divisors is (x + 1) * (y + 1) * (z + 1)

Algorithm to find the solution is:

package projecteuler;
/**
*
* @author Vasanth Raja Chittampally
*/
public class ProjectEuler {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
long sum=0;
out:for (int i = 45000; ; i++) {
sum=i*(i+1)/2;
boolean isPrime=true;
for(int k=2;k<=Math.sqrt(sum);k++)
{
if(sum%2==0)
{
isPrime=false;
break;
}
else if(sum%k==0) {
isPrime=false;
break;
}
}
if(isPrime) continue out;
long no=sum;
int div=2;
int count=0;
int noOfDiv=1;
long temp=no;
while(no%2==0)
{
no=no/2;
count++;
}
div++;
noOfDiv=noOfDiv*(count+1);
count=0;
while(no!=1) {
count=0;
while(no%div==0)
{
no=no/div;
count++;
}
div+=2;
noOfDiv=noOfDiv*(count+1);
}
if(noOfDiv>=500) {
System.out.println(“”+sum);
break;
}
}

}

}

I tested it with java worked fine and got the answer correct. I don’t want to post the answer here. Try out yourself.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: