Project Euler Problem 12: Highly divisible triangular number

Algorithm Pseudocode for Naive Approach

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

1. Loop for each sum until we get a sum whose number of divisors are greater than 500.
2. To find the number of divisors, iterate through each number, beginning at 1 up until the sqrt(input).
3. 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.
4. Handle the one exception if our input is a perfect square. In this case, increment by only one.

Code for Naive Approach in Java

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.

Finding prime factors and their occurrences

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² x 7¹. 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⁰ = 1, once as a 2¹ = 2, or twice as a 2² = 4. For 7, it may not appear at all 7⁰ = 1, or appear as a 7¹ = 7.

Algorithm Pseudocode

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.

1. Per each sum value, obtain a HashMap with all prime factors and their corresponding number of occurrences.
2. Use the HashMap to generate the number of possible factors.
3. 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³ x 5² = 200.

Working Code in Java

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.

Full runnable code

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!