Triangulate the divisors and divide the triangulars

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 223*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 443222*2 = 768 divisors.

public class ProjEuler12 {

    public static long triangleNumberN(long n) {
        if (n  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?

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(mn) = \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.

StackExchange Code Review Q#84439, answer score: 4