Project Euler Problem 12 - triangle number with 500 divisors

Question

I've just done Problem 12 of Project Euler:

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

The \$N\$'th triangle number is the sum of all natural numbers from \$1\$ to \$N\$, for example, the 5th triangle number is \$1 + 2 + 3 + 4 + 5 = 15\$

I get the correct answer in around 2.5 seconds.

I was wondering if anyone could suggest anything that could improve the performance of the program, or improve the code in general.

public class Problem12 {

public static void main(String[] args) {
    double startTime = System.currentTimeMillis();
    run();
    double endTime = System.currentTimeMillis();
    System.out.println("Took "+((endTime - startTime) / 1000)+" seconds"); 
}

public static void run() {
    boolean go = true;
    long number = 1;
    long nextNum = 2;
    int maxDivisors = 500;
    while (go) {
        if (countDivisors(number) > maxDivisors) {
            System.out.println("The first triangle number with over "+maxDivisors+" divisors is: "+number);
            go = false;
        }
        else {
            number += nextNum;
            nextNum++;
        }
    }
}

public static long countDivisors(long number) {
    long divisors = 0;
    for (int i = 1; i*i <= number; i++) {
        if (number % i == 0) {
            divisors+=2;
        }
    }
    return divisors;
}
}

Answer 1

There is an error in your countDivisors() function, the result is one too large for a perfect square, i.e. countDivisors(25) returns 4 instead of 3. Also the loop variable i should be a long to avoid an integer overflow when testing i*i <= number. A correct version would be

public static long countDivisors(long number) {
    long divisors = 0;
    for (long i = 1; i*i <= number; i++) {
        if (number % i == 0) {
            if (i*i < number) {
                divisors += 2; // i and number/i are (different) divisors
            } else {
                divisors += 1; // i == number/i is a divisor
            }
        }
    }
    return divisors;
}

The run() function can be simplified slightly, the boolean go variable is not really necessary:

public static void run() {
    long number = 1;
    long nextNum = 2;
    int maxDivisors = 500;
    while (countDivisors(number) <= maxDivisors) {
        number += nextNum;
        nextNum++;
    }
    System.out.println("The first triangle number with over "+maxDivisors+" divisors is: "+number);
}

To improve the performance, use the fact that

• triangle numbers are of the form \$ n \, (n+1)/2 \$, and
• the "number-of-divisors function" \$ \sigma_0(n) \$ is multiplicative, i.e. \$ \sigma_0(m \, n) = \sigma_0(m) \, \sigma_0(n) \$ if \$ m, n \$ are relative prime (see Divisor Function).

If \$ n \$ is even then \$ n/2 \$ and \$ n+1 \$ are relative prime, and if \$ n \$ is odd then \$ n \$ and \$ (n+1)/2 \$ are relative prime. This leads to the following implementation

public static void run() {
    long n = 1;
    int maxDivisors = 500;
    while (countDivisors((n+1)/2) * countDivisors(n) <= maxDivisors) {
        n++;
        if (countDivisors(n/2) * countDivisors(n+1) > maxDivisors) {
            break;
        }
        n++;
    }
    long number = n*(n+1)/2;
    System.out.println("The first triangle number with over "+maxDivisors+" divisors is: "+number);
}

which is faster because the countDivisors() function is called with smaller numbers. On my computer it reduces the time from 0.6 to 0.02 seconds.

A faster implementation of countDivisors() would use the prime factorisation of the given number, as explained in the above referenced Wikipedia article.

Answer 2

• Performance.

  ProjectEuler problems are rather about math than programming. To solve problem 12 efficiently you need to learn some number theory facts, specifically the multiplicative property of a number of divisors function \$\sigma(n)\$. You also have to observe that a triangular number is a product of two coprimes. Then you may combine that knowledge into a very efficient algorithm.

• General notes.

  bool go is not necessary. When the desired number is found, you can return, or break the loop, immediately.

  countDivisors apparently has a bug: a perfect square counts its root twice.

Answer 3

public static long countDivisors(long number) {
    long divisorCount = 0;

    int i = 1;
    while ( i*i < number ) {
        if ( number % i == 0 ) {
            divisorCount += 2;
        }

        i++;
    }

    if ( i*i == number ) {
        divisorCount++;
    }

    return divisorCount;
}

Your original version did not check for the possibility that number was a perfect square. The revised version from Martin R does check, but it does so on every found factor. We can do better than that. This version only checks once at the end. Note: this may not make an actual performance difference. The main reason that I like it is that it is clearer about when the check might be done.

I switched from the for loop to the while to expand the scope of i. This allows us to check it outside the loop.

We do not need to check that number % i == 0 on that last check, as that will always be true if number is i squared. It's enough just to check that the square of i is number.

public static long run(int maxCount) {
    long n = 1;
    while ( countDivisors((n+1)/2) * countDivisors(n) <= maxCount ) {
        n++;
        if ( countDivisors(n/2) * countDivisors(n+1) > maxCount ) {
            break;
        }
        n++;
    }

    return n*(n+1)/2;
}

I changed maxDivisors to maxCount to make it clearer what it is tracking. The name maxDivisorCount would be even clearer but may be overkill.

I changed maxCount from a variable declaration to a method parameter. This makes it easier to change its value if desired. You can even run multiple times with different values now. This also comes under the category of avoiding magic numbers. If we're defining a magic number, I'd rather put it in main than run.

I changed run to return a value rather than perform output. This improves the algorithm timing, as it reduces overhead. It also makes the function more flexible. If you wanted to call it and then use the result, you could. The original version only displayed the result.

public static void main(String[] args) {
    int maxCount = 500;

    double startTime = System.currentTimeMillis();
    long number = run(maxCount);
    double endTime = System.currentTimeMillis();

    System.out.println("The first triangle number with more than " + maxCount + " divisors is: " + number);
    System.out.println("Took " + ((endTime - startTime) / 1000) + " seconds"); 
}

This is just changed to pass a parameter to run, take a return value, and display.