Euler Project Help (Problem 12) - Prime Factors and the like

Question

I hate to have to ask, but I'm pretty stuck here.

I need to test a sequence of numbers to find the first which has over 500 factors: http://projecteuler.net/index.php?section=problems&id=12

-At first I attempted to brute force the answer (finding a number with 480 after a LONG time)

-I am now looking at determining the prime factors of a number and then use them to find all other factors.

I am currently at the stage where I can get an array of prime factors for any number I input - i.e 300 has the prime factors 2 2 3 5 5

Using this array of prime factors I need to be able to calculate the remaining factors - This is the part I am stuck on. Basically, as I understand it, I need to calculate ALL possible combinations of the numbers in the array...

i.e 2 * 2
2 * 2 * 3
2 * 2 * 3 * 5
2 * 3
2 * 3 * 3
...and so forth - But where it gets interesting is with things like...
2 * 5
2 * 3 * 5
...i.e Numbers which are not adjacent to each other in the array

I can't think of a way to code this in a generic fashion for any length array...

I need help! P.S - I am working in Java

EDIT: My brute force code - As it has been suggested brute forcing the problem will work and so there may be an error in my code :(

package euler.problem12;

public class Solution {

    public static void main(String[] args) {
        int next = 1;
        int triangle = 0;
        int maxFactors = 0;

        while(true) {
            triangle = triangle + next;

            int factors = 1;
            int max = (int) triangle / 2;

            for(int i = 1; i <= max; ++i) {
                if(triangle % i == 0) {
                    factors ++;
                }
            }

            if(factors > maxFactors) {
                maxFactors = factors;

                System.out.println(triangle + "\t" + factors);
            }

            next++;
        }
    }
}

Answer 1

As far as I can tell, question 12 doesn't mention anything about prime numbers? Is this the one you're looking at?

The sequence of triangle numbers is generated by adding the natural numbers...

If so, then perhaps not thinking about primes will help? ;)

Answer 2

OK, second attempt as I was making things far too difficult.

Answer is given here: http://mathforum.org/library/drmath/view/57151.html

If you factor a number into its prime power factors, then the total number of factors is found by adding one to all the exponents and multiplying those results together. Example: 108 = 2^2 * 3^3, so the total number of factors is (2+1) * (3+1) = 3 * 4 = 12. Sure enough, the factors of 108 are 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, and 108. This happens because to be a factor, a number must have the same primes, and raised to the same or lower powers.

So if you know the prime factors, you just need to count the repeated ones and use the above calculation to work out the number of factors.

Answer 3

Possibly 3 months too late, but here goes...

I see that answer two has privided the function to give you the answer you require, but in answer to your original question on how you generate all the factors assuming you need to for some reason, then here's how you do it:

Assuming that you have the factors in an array:

int[] primeFactors = new int[] {2, 2, 3, 5, 5};

What you need to do is recurse every in-order permutation for each possible depth, and then reduce the resulting result set to just the unique values.

I'll explain what I mean: "In-order permutation": assuming you start at position 0 of the array, the next element must be 1, 2, 3 or 4, if you start from 1 then the next one must be 2, 3 or 4 and so on.

"Each possible depth": each single factor, then any two factors, then any three factors and so on until you get to all five factors.

"Reduce the set": If you take two elements, say 0&3, 0&4, 1&3 or 1&4 they all give you 2 * 5 = 10, they all provide the factor 10, so you need to winnow your set to just distinct values. (Phew, this is getting longer than I expected... :))

The way to do this is to use two methods, one to select the maximum depth of recursion, kick off the recustion and the winnow the final results, and the other to recurse the values:

public static void main(String[] args) {
    int[] primeFactors = new int[] {2, 2, 3, 5, 5};
    List<Integer> allFactors = getAllFactors(primeFactors);
    for (int factor : allFactors) {
        System.out.println("Factor: " + factor);
    }
}

private static List<Integer> getAllFactors(int[] primeFactors) {
    Set<Integer> distinctFactors = new HashSet<Integer>();
    for (int maxDepth = 0; maxDepth <= primeFactors.length; maxDepth++) {
        permutatPrimeFactors(0, maxDepth, 0, 1, primeFactors, distinctFactors);
    }
    List<Integer> result = new ArrayList<Integer>(distinctFactors);
    Collections.sort(result);
    return result;
}

private static void permutatPrimeFactors(int depth, int maxDepth, int minIndex, int valueSoFar, int[] primeFactors, Set<Integer> distinctFactors) {
    if (depth == maxDepth) {
        distinctFactors.add(valueSoFar);
        return;
    }

    for (int index = minIndex; index < primeFactors.length; index++) {
        permutatPrimeFactors(depth + 1, maxDepth, index + 1, valueSoFar * primeFactors[index], primeFactors, distinctFactors);
    }
}

The getAllFactors uses a Set to make sure we only get distinct values, than adds them to a list and sorts that so that we can display the factors in order.

While permutatPrimeFactors, generates from zero terms (factor = 1) though to all terms (factor = 1 * 2 * 2 *3 * 5 * 5 = 300).

Hope that helps.