3
\$\begingroup\$

Highly divisible triangular number, my solution

My solution of challenge from Project Euler takes too much time to execute. Although on lower numbers it works fine. Anyone could look up to my code and give me any advice to improve it? The content of the task is:

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, ...

Let us list the factors of the first seven triangle numbers:

 (1: 1),
 (3: 1,3),
 (6: 1,2,3,6),
(10: 1,2,5,10),
(15: 1,3,5,15),
(21: 1,3,7,21),
(28: 1,2,4,7,14,28).

We can see that 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?

 public static void main(String[] args) {
        int sum = 0;
        int count = 0;
        for (int i = 1; i <= Integer.MAX_VALUE; i++) {
            sum += i;
            for (int j = 1; j <= sum; j++) {
                if (sum % j == 0) {
                    count++;
                }
            }
            if (count > 500) {
                System.out.println(sum);
                break;
            } else {
                count = 0;
            }
        }

    }
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Infinite loop

In this loop, for (int i = 1; i <= Integer.MAX_VALUE; i++) { ... }, since i is an int, it is impossible for i <= Integer.MAX_VALUE to ever be false. It looks like you are trying to put an upper limit on the search, however, it will not actually stop the search if the solution isn't found before i rolls over.

Counting

You always have to start counting the factors of sum at zero. It makes no sense to have resetting count = 0; to be conditional on count > 500.

    public static void main(String[] args) {
        int sum = 0;
        for (int i = 1; i <= Integer.MAX_VALUE; i++) {
            int count = 0;  // Initialize count to zero here!
            ...
            if (count > 500) {
                System.out.println(sum);
                break;
            }
        }
    }

Counting Factors

You are doing a lot of pointless checks here:

            for (int j = 1; j <= sum; j++) {
                if (sum % j == 0) {
                    count++;
                }
            }

After reaching j reaches sum/2, you will not find any other divisors of sum until you reach j == sum. You could skip all those trial divisions with:

            count = 2;  // '1' and 'sum' are always divisors (tiny white lie if sum=1)
            limit = sum / 2;
            for (int j = 2; j <= limit; j++) {
                if (sum % j == 0) {
                    count++;
                }
            }

Counting pairs of factors

If j is a divisor of sum, then sum/j is also a divisor of sum. When you find one divisor, you've found two, unless j == sum/j, in which case you've found only one. With this improvement, you only need trial divisions up to \$\sqrt{sum}\$

            limit = (int) Math.sqrt(sum);
            count = 2;
            for (int j = 2; j <= limit; j++) {
                if (sum % j == 0) {
                    count += 2;
                }
            }
            if (limit * limit == sum) {
                count--; // sum is perfect square: correct for divisor counted twice.
            }

Since 1 is a perfect square, this also fixes the tiny white lie of the previous implementation.

Triangle numbers

A quick search on Triangle numbers will tell you that

$$ T_n = \frac{n * (n + 1)}{2} $$

This means you don't need to count sum += i, you can just calculate the triangle number directly. By itself, that doesn't save you much time but ...

Relatively Prime

n and n + 1 will never have any common factors other than 1. This means that n * (n + 1) / 2 will have the combinations of factors of n and n + 1 mixed together.

$$T_7 = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 7 * ( 7 + 1 ) / 2$$ $$= 7 * ( 8 ) / 2$$ $$= 7 * 4$$

The factors of 7 are 1 & 7, the factors of 4 are 1, 2, and 4. The factors of 28 will include 1 * 1, 1 * 2, 1 * 4, 7 * 1, 7 * 2, and 7 * 4. Two factors of 7, times three factors of 4 gives you 2 * 3 = 6 combinations of factors total!

Thus, to solve this problem quickly, simply generate the triangle numbers as n*(n+1)/2 and determine the factors of n and (n+1)/2 or the factors of n/2 and (n+1), depending on whether n is even or odd, and multiply the number of factors together to get count. If that is not greater than 500, repeat with the next ++n. Bonus, since the next triangle number will be (n+1)*(n+2)/2, you've already computed the factors of the first term (either (n+1) or (n+1)/2) which you can use on the next iteration.

Implementation left to student.

\$\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.