5
\$\begingroup\$

Project Euler 12 - Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be \$1 + 2 + 3 + 4 + 5 + 6 + 7 = 28\$. The first ten terms would be: \$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\$

(...) 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

I did spend quite a bit of time on this one to figure out a faster solution than what I first attempted. My first, very naive approach, to finding the number of divisors for a number was to loop through all the numbers and count them, like this:

public static long numDivisors(long number) {
    long count = number == 1 ? 1 : 2;
    for (int i = 2; i <= number / 2; i++) {
        if (number % i == 0) {
            count++;
        }
    }
    return count;
}

I knew there was a faster approach. And I didn't give up until I found one.

I realized, after factorizing some numbers, that the fastest way is to keep a track of the unique prime factors that make up the number, and use them to calculate the number of divisors.

For example, 36. It has 9 divisors in total, 1, 2, 3, 4, 6, 9, 12, 18, 36. We know though that 36 is 2*2*3*3. That's 2 factors of 2 and 2 factors of 3. So by choosing 0-2 2's and 0-2 3's we can get the 9 divisors of 36.

The same goes for a bigger number, such as 32063349528. If we prime-factorize it, it is 2 * 2 * 2 * 3 * 3 * 3 * 7 * 7 * 17 * 19 * 83 * 113. So 4*4*3*2*2*2*2 = 768 divisors.

public class ProjEuler12 {

    public static long triangleNumberN(long n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n must be positive: " + n);
        }
        return (1 + n) * n / 2;
    }

    public static int divisorCount(long number) {
        if (number <= 0) {
            throw new IllegalArgumentException("number must be positive: " + number);
        }
        int divisors = 1;
        long lastNum = 0;
        int lastCount = 0;
        while (number != 1) {
            if (number % 2 == 0) {
                lastCount++;
                number /= 2;
                continue;
            }
            for (long i = 3; i <= number; i += 2) {
                if (number % i == 0) {
                    if (lastNum != i) {
                        divisors *= lastCount + 1;
                        lastCount = 1;
                        lastNum = i;
                    } else {
                        lastCount++;
                    }
                    number /= i;
                    break;
                }
            }
        }
        return divisors * (lastCount + 1);
    }

    public static void main(String[] args) {
        long result = LongStream.iterate(1, i -> i + 1)
                .map(ProjEuler12::triangleNumberN)
                .filter(n -> divisorCount(n) > 500)
                .findFirst().getAsLong();
        System.out.println(result);
    }

}

Any improvements possible? Can it be made even faster? Is the naming just as good as you would expect?

\$\endgroup\$
4
\$\begingroup\$

Can it be made even faster?

Sure.

Fact number one. An n'th triangular number is \$\frac{n(n+1)}{2}\$

Fact number two. A number of divisors (aka \$\sigma(n)\$) is multiplicative, that is \$\sigma(m*n) = \sigma(m)*\sigma(n)\$ for coprime m and n.

Fact number three. \$n\$ and \$n + 1\$ are coprime.

Which means you don't have to factorize (fairly large) triangular numbers. Instead, you only need to factorize \$n\$ and \$n+1\$; in fact, since one of them is even, and contributes as a number twice that small, at most one number needs to be factorized at each iteration. You need to memoize factorizations though.

And of course a precomputed prime numbers table may help.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.