Question:
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:
Let us list the factors of the first seven triangle numbers:
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?
Let's start with the most naive, straight-forward solution.
public static int getFirstTriNumOver500Naive() {
int n = 1;
int sum = 1;
while (getNumDivisors(sum) < 500) {
sum += ++n;
}
return sum;
}
while (getNumDivisors(sum) < 500) {
sum += ++n;
}
Running with this method, we finished in 0.324 seconds. Can we do better? Of course we can!
76576500
Completed in 323805979 nanoseconds.
If we break down our input value into prime factors, then we may have a way to find the number of possible factors without having to go through and testing each value. Let's look at this more closely.
Let's say we have the value 28. We can find out how many possible factors we have by writing out all the factors to 28: 1, 2, 4, 7, 14 and 28. Looks like we have six.
Another way to write 28 is by its prime factors, e.g. 22 x 71. Notice how the 2 occurs twice, and the 7 occurs just once. Now to find all the possible variations of factors, we can use combinations. (2+1) x (1+1) = 6, which is the same value we found above.
To explain how this works, think about the factors that can be generated by two 2's and one 7. We have three ways the 2 can appear - not at all as 20 = 1, once as a 21 = 2, or twice as a 22 = 4. For 7, it may not appear at all 70 = 1, or appear as a 71 = 7.
Back to the problem. We need to find a way to find each prime factor and its corresponding occurrences. Sounds like we need an associative array; the closest data type in Java is the HashMap. We actually solved this exact problem before, so we'll use the same code.
Basically, if we input the value 200 into our getPrimeFactors method, we want a HashMap like {2 => 3, 5 => 2} since 23 x 52 = 200.
public static int getFirstTriNumOver500() {
int possibilities = 1;
int n = 1;
int sum = 1;
while(possibilities < 500) {
possibilities = 1;
HashMap<Integer, Integer> factors = getPrimeFactors(sum);
for (Integer key : factors.keySet()) {
possibilities *= factors.get(key)+1;
}
sum += ++n;
}
return sum - n;
}
public static HashMap<Integer, Integer> getPrimeFactors(int input) {
HashMap<Integer, Integer> factors = new HashMap<>();
int possiblePrimeFactor = 2;
while (input != 1) {
while (input % possiblePrimeFactor == 0) {
if (factors.get(possiblePrimeFactor) == null) {
factors.put(possiblePrimeFactor, 1);
} else {
factors.put(possiblePrimeFactor, factors.get(possiblePrimeFactor)+1);
}
input /= possiblePrimeFactor;
}
possiblePrimeFactor++;
}
return factors;
}
This implementation runs about a third faster than the previous strategy.
76576500
Completed in 323805979 nanoseconds.
import java.util.HashMap;
public class HighlyDivisibleTriangularNumber {
public static void main(String[] args) {
long startTime = System.nanoTime();
System.out.println(getFirstTriNumOver500());
long endTime = System.nanoTime();
System.out.println("Completed in " + (endTime-startTime) + " nanoseconds.");
startTime = System.nanoTime();
System.out.println(getFirstTriNumOver500Naive());
endTime = System.nanoTime();
System.out.println("Completed in " + (endTime - startTime) + " nanoseconds.");
}
public static int getFirstTriNumOver500() {
int possibilities = 1;
int n = 1;
int sum = 1;
while(possibilities < 500) {
possibilities = 1;
HashMap<Integer, Integer> factors = getPrimeFactors(sum);
for (Integer key : factors.keySet()) {
possibilities *= factors.get(key)+1;
}
sum += ++n;
}
return sum - n;
}
public static int getFirstTriNumOver500Naive() {
int n = 1;
int sum = 1;
while (getNumDivisors(sum) < 500) {
sum += ++n;
}
return sum;
}
public static int getNumDivisors(int input) {
int factor = 0;
/**
* Only up to the square root.
* If there exists a factor between input and sqrt(input)
* then that value will have a corresponding factor between 3 and sqrt(input)
*/
for (int i = 1; i <= Math.sqrt(input); i++) {
if (i*i == input) {
factor++;
} else if (input % i == 0) {
factor += 2;
}
}
return factor;
}
public static HashMap<Integer, Integer> getPrimeFactors(int input) {
HashMap<Integer, Integer> factors = new HashMap<>();
int possiblePrimeFactor = 2;
while (input != 1) {
while (input % possiblePrimeFactor == 0) {
if (factors.get(possiblePrimeFactor) == null) {
factors.put(possiblePrimeFactor, 1);
} else {
factors.put(possiblePrimeFactor, factors.get(possiblePrimeFactor)+1);
}
input /= possiblePrimeFactor;
}
possiblePrimeFactor++;
}
return factors;
}
}
Came up with a better solution or have a question? Comment below!