Triangle Numbers Divisors

[Sam Benry]

Problem:

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 the 7th triangle number, 28, is the first triangle number to have over five divisors.

Which is the first triangle number to have over five-hundred divisors?

As always, the code is not generating a result,
should I use BigInteger instead of long?
is there a better way to do this?

public class TriangleNumbers 
{
public static void main(String[] args) 
{
int i=2,triNbr=1;
long counter=0;
while(counter <= 500)
{
counter = 0;
triNbr += i;
i++;
for(int j=1;j<=triNbr;j++)
if(triNbr % j == 0) counter++;
}
System.out.println(triNbr);
}
 
}

[Campbell Ritchie]

You are resetting the ounter to 0 every time you run the while loop. There may be other errors; I haven't checked.

[Henry Wong]

As always, the code is not generating a result,
should I use BigInteger instead of long?
is there a better way to do this?

Hate the point out the obvious, but you really need to learn how to debug a program. This problem as with the other "always" programs can be debugged with some interium results printouts within the loop.

Henry

[Rob Spoor]

As a side node, for any triangle number "n", you can calculate the value using only simple arithmetic:

n * (n + 1) / 2

This has been proven quite often; it is even an exercise for students to prove this themselves.

[Sam Benry]

@Campbell Ritchie
the counter is reset to zero to count how many divisors each number has, or else we will be counting the sum of divisors for all the numbers

@Henry Wong
this code works for small numbers, but when the numbers get large, each loop will loop twice to that number which will take forever to end... but I cant figure any other way to do this

@Rob Prime
I'll check that out, thanks

I still need help, I need a better way to do this

[Campbell Ritchie]

Yes, I see what you mean. I was mistaken. Sorry.

[Neelesh A Korade]

You can optimize on the inner for loop-

The loop termination condition can be changed to j<= triNbr/2.

Reasoning-
You don't have to check for divisors of a number N in the range (N/2)+1 ... N as there are never going to be any, except for the number N itself.

A further optimization could be made when N is not an even number (i.e. it is an odd number).

[Sam Benry]

@Neelesh A Korade
the triNbr/2 might help a little bit, but not much, since the loop is very large anyway...

and what if the number is odd? couldnt it have a 500 divisors if its odd? why?

[Campbell Ritchie]

It needs more optimisations than that; it is cubic complexity and runs in O(n^3) time. You need to work out how to reduce the counting space.

So 1 and N are divisors of N: Right, start from potentialDivisor = 2 and divisorCount = 2.
If it divides by 2, there will be a 2nd divisor, N / 2, and if it divides by 3 there will also be N / 3.

Work out how to terminate your loop and reduce the complexity. Otherwise it will take all day to run.

[Sam Benry]

http://blog.plover.com/oops/triangular-phi.html