**Question:**

The sequence of triangle numbers is generated by adding the natural numbers. So the `7 ^{th}` triangle number would be

Let us list the factors of the first seven triangle numbers:

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?

Related Tags:

Let's start with the most naive, straight-forward solution.

- Loop for each sum until we get a sum whose number of divisors are greater than 500.
- To find the number of divisors, iterate through each number, beginning at 1 up until the sqrt(input).
- Each time we find a factor less than the sqrt(input), there exists a corresponding factor that is greater than sqrt(input). Thus, increment the number of factors found by two.
- Handle the one exception if our input is a perfect square. In this case, increment by only one.

```
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. `2 ^{2} x 7^{1}`. 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 `2 ^{0} = 1`, once as a

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.

- Per each sum value, obtain a HashMap with all prime factors and their corresponding number of occurrences.
- Use the HashMap to generate the number of possible factors.
- If number of factors calculated is > 500, stop. If not, repeat.

Basically, if we input the value `200` into our getPrimeFactors method, we want a HashMap like `{2 => 3, 5 => 2}` since `2 ^{3} x 5^{2} = 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!

Next Challenge: Index of a substring