Clever Geek Handbook

Euler Project Reference (Task 12) - Key Factors and the Like

I can't wait to ask, but I'm pretty stuck here.

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

-First, I tried to iterate over the strength of the answer (finding a number with 480 after a LONG time)

-I am now looking at defining simple number factors and then using them to find all the other factors.

I am currently at a stage where I can get an array of simple factors to input any number i - i.e. 300 has main odds 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 numbers in an array ...

those. 2 * 2
2 * 2 * 3
2 * 2 * 3 * 5
2 * 3
2 * 3 * 3
... etc. - But where it gets interesting, with things like ... 2 * 5
2 * 3 * 5
... ie Numbers that are not adjacent to each other in an array

I can't think of a way to generally encode this for any length array ...

I need help! PS - I am working in Java

EDIT: my brute force code. As suggested, a brute force problem will work, so there might 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++;
        }
    }
}
+1


source to share


3 answers


As far as I can tell, question 12 says nothing about prime numbers? Is this the one you are looking at?

The triangle number sequence is generated by adding natural numbers ...



If so, then maybe not to think about the simple ones?;)

+2


source


OK, second try as I was doing things too hard.

The answer is given below: http://mathforum.org/library/drmath/view/57151.html



If you define a number in its basic power factors, then the total number of factors can be found by adding one to all 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. Of course, the coefficients 108 are 1, 2, 3, 4, 6, 9 , 12, 18, 27, 36, 54 and 108. This is because, in order to be a factor, a number must have the same prime, and rise to the same or lower powers.

So, if you know the main factors, you just need to count the duplicates and use the above calculation to determine the number of factors.

+9


source


Maybe 3 months too late, but here it goes ...

I see that answer two has split the function to give you the answer you want, but in response to your original question about how you generate all the factors that suggest what you need for some reason, this is how you do it :

Assuming you have the factors in the array:

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

What you need to do is overwrite each permutation at every possible depth, and then reduce the resulting result set to unique values.

I'll explain what I mean: "Permutation is OK": if you start at position 0 of the array, the next element must be 1, 2, 3 or 4, if you start at 1, then the next must be 2, 3 or 4 etc.

"Every possible depth": every single factor, then any two factors, then any three factors, and so on, until you reach all five factors.

"Decrease set": if you take two elements, say 0 and 3, 0 and 4, 1 and 3 or 1 and 4, they all give you 2 * 5 = 10, they all provide a factor of 10, so you need to output your set only for individual values. (Ugh, this is taking longer than I expected ... :))

The way to do this is to use two methods, one to select the maximum recursion depth, start processing and output the final results, and the other to return 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);
    }
}

GetAllFactors uses Set to make sure we only get individual values, which adds them to the list and sorts them so that we can display the factors in order.

Whereas permutatPrimeFactors is generated from zero members (factor = 1), albeit for all members (factor = 1 * 2 * 2 * 3 * 5 * 5 = 300).

Hope it helps.

+1


source






More articles:


All Articles