Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!

# Triangle Numbers Divisors

Sam Benry
Ranch Hand
Posts: 89
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?

Campbell Ritchie
Sheriff
Posts: 49788
69
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
author
Marshal
Posts: 21408
84
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
Sheriff
Posts: 20608
63
As a side node, for any triangle number "n", you can calculate the value using only simple arithmetic:

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

Sam Benry
Ranch Hand
Posts: 89
@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
Sheriff
Posts: 49788
69
Yes, I see what you mean. I was mistaken. Sorry.

Greenhorn
Posts: 26
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
Ranch Hand
Posts: 89
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
Sheriff
Posts: 49788
69
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
Ranch Hand
Posts: 89