views:

3561

answers:

3

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++;
        }
    }
}
+2  A: 

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? ;)

Martin
Yes - I need to find the first one which has over 500 divisors. It is pretty much impossible to brute force every divisor - Instead I believe I can find the prime factors and use those to calculate the remaining divisors.
Richie_W
It's not that hard. I have a brute forcing approach (also in Java) that completes in around 10 seconds on my MacBook Pro... So if you have your algorithms correct, you should be able to get something that returns a result pretty quickly. Don't be afraid of brute force early on in the questions!
Martin
Perhaps there is an error in my old code (though I wouldn't know why as I have verified that it correctly for smaller numbers). I get a 480 divisor number at around the 17.9 million mark...after that the program is way too slow
Richie_W
I think you're making this too hard for yourself. Start with something that will list _ALL_ factors of a number (prime or otherwise). Then loop through increasing numbers until you find a list that's >500 factors and you're done.
Martin
And don't forget - factors are pairs - so for 300 you have factors of 1, 300, 2, 150, 3, 100, etc
Martin
I was doing. I posted the old code in my edit. Cheers
Richie_W
Your code is close - but you're doing two things that are stepping on each other - what is "int max..." (btw there's a better way to do this), and what is "factors++"? Beyond that, you're pretty close
Martin
Factors = The number of divisors found for the current number (There is a bug / cheat which means I need to start that value at 1) Max = the max number to try and get new divisors from...i.e if the number was 10 then anything above 5 would be useless as it couldnt possibly result in an integer value
Richie_W
so, you're saving yourself cycles by only checking half of the available numbers for matching factors. However, each factor has a matching pair. Where does this occur in relation to your boundary?
Martin
Matching pairs dropped the penny for me. Thank you so much. :)
Richie_W
Also, your upper limit can be sqrt(triangle) rather than triangle/2. Say you're factoring 100. Your code is testing every number from 1 to 50. You only need to test 1 to 10, then double the result (subtracting 1 in this case because 10 is an exact square root).
Dave Costa
+6  A: 

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.

Paul
Cheers! I'm sure this info will come in hany later on. Many thanks!
Richie_W
And when finding the prime factors of a triangle number in particular, you get a head start because you already know that T(n) is divisible by either n or (n+1): to be precise, it's divisible by whichever one of them is odd.
Steve Jessop
+1  A: 

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.