CODEWITHSUNDEEP
javascriptmath
Corey Ogburn
Corey Ogburn

Reputation: 24759

Prime Factorization and Sum of Divisors not working?

So I restarted Project Euler when I lost all my code for it. I'm at problem 23. I know how to do it and I've done it before but it's not working right now and I've been trying to tackle it for so long, I can barely think straight. I'm using NodeJS this time around.

According to this really simplified article, I can use the prime factorization to figure out the sum of a number's divisors. So I have these two functions:

Util.GetPrimeFactors = function (val) {
    var init = val;
    var num = 2;
    var primes = {};
    while (val > 1) {
        if (val % num == 0) {
            if (num == init) return [];// prevent prime numbers from including themselves
            if (primes[num]) {
                primes[num]++;
            } else {
                primes[num] = 1;
            }
            val /= num;
        } else {
            num++;
        }
    }
    return primes;
}

Util.SumOfDivisors = function (val) {
    var primes = Util.GetPrimeFactors(val);
    var coeff = primes[0];
    var count = 0;
    var total = 1;
    for (var i in primes) {
        count++;
        if (primes[i] > 1) {
            var n = parseInt((Math.pow(parseInt(i), primes[i] + 1) - 1) / (parseInt(i) - 1))
            console.log(n);
            total *= n;
        } else {
            var n = parseInt(i) + 1
            console.log(n);
            total *= n;
        }
    }
    if (count == 1) return 1;
    return total;
}

If I call GetPrimeFactors(12) I get this object: { '2': 2, '3': 1 } which represents 2^2+3, the name is the base value and the value is the exponent. SumOfDivisors uses that object to do the math in the above linked article. The problem is that according to the Project Euler problem, 12 is the first abundant number. If I run 6 through SumOfDivisors, I get the proper prime factors (the object { '2': 1, '3': 1 }) but it results in SumOfDivisors returning 12 making 6 look abundant. If you add up factors the inefficient way (bullet B in the math article) then you obviously get the factors 1, 2, and 3 which makes 6 a perfect number.

I remember in my old C# code that I used this same technique: finding primes and using them to sum divisors. But I didn't have this problem with 6 (and probably many more numbers). I'm at a lose for what I'm doing wrong here. What am I doing wrong when I'm finding the sum of divisors? Is this technique known not to work for certain values? Am I glazing over a special case? Am I snagged on a Javascript gotcha?

Upvotes: 0

Views: 503

Answers (1)

Jesus Ruiz
Jesus Ruiz

Reputation: 1385

Your code is doing exactly what the article says.

Project Euler actually asks for the sum of proper divisors:

28 would be 1 + 2 + 4 + 7 + 14 = 28

While the article specifies the algorithm for the sum of positive integral divisors:

12 would be 1 + 2 + 3 + 4 + 6 + 12 = 28

Note that the first case doesn't include the number itself, while the second does. That is why 6 is not abundant (1 + 2 + 3 = 6), but the sum of its integral divisors is 12 (1 + 2 + 3 + 6).

Upvotes: 1

Related Questions