Triangulate the divisors and divide the triangulars

Question

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?

Answer 1

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.