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

Project Euler Problem 12: 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?

Solution: This problem can be solved by simply dividing the numbers iteratively and finding out the no. of factors it have. To find the factors a number have we divide it by prime numbers and its multiples.

This is an brute force implementation and takes approximately an hour to complete.


Java Program to hold processed information


package library;
import java.util.List;
public class DivisorDetails {
// Contains the count of divisors/factors of a given number
public long noOfDivisors;
// Contains the divisors/factors of a given number
public List<Long> divisors;
}

Java Program to find the number of factors of a triangle number.


package evaluator;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import library.DivisorDetails;
import library.GeneratePrime;
import library.TriangleNumbers;
public class NoOfDivisors {
public DivisorDetails noOfDivisorBruteForce() {
long triangleNumber = 1, naturalNum = 1;
TriangleNumbers triNum = new TriangleNumbers();
FindFactors factors = new FindFactors();
DivisorDetails result = new DivisorDetails();
long largest = 0;
while (result.noOfDivisors < 500) {
triangleNumber = triNum.nextTriangleNumber(triangleNumber,
naturalNum++);
result = factors.findFactorsBruteForce(triangleNumber);
if(result.noOfDivisors > largest){
largest = result.noOfDivisors;
System.out.println("Triangle number:t"
+ triangleNumber);
System.out.println("Number of factors:t"
+ result.noOfDivisors);
}
}
System.out.println("Triangle number:t" + triangleNumber);
return result;
}
}

Java Program to find the next triangle number.


package library;
public class TriangleNumbers {
public long nextTriangleNumber(long triangleNumber, long naturalNum){
triangleNumber = triangleNumber + (naturalNum + 1);
return triangleNumber;
}
}

Java Program to find the factors for a given number.


package evaluator;
import java.util.ArrayList;
import library.DivisorDetails;
public class FindFactors {
/* Find the factors for a given number and
return an array containing factors and its count. */
public DivisorDetails findFactorsBruteForce(long triangleNumber){
DivisorDetails details = new DivisorDetails();
details.divisors = new ArrayList<Long>();
for(int i=1;i<=triangleNumber/2;i++){
if(triangleNumber % i == 0){
details.noOfDivisors += 1;
details.divisors.add((long) i);
}
}
details.noOfDivisors += 1;
details.divisors.add(triangleNumber);
return details;
}
}

Keep coding. Enjoy !!!

Leave a Reply

Your email address will not be published. Required fields are marked *