# Triangle Numbers Divisors

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

Problem:

As always, the code is not generating a result,

should I use BigInteger instead of long?

is there a better way to do this?

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: 49382

62

posted 8 years ago

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

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

posted 8 years ago

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.

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

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

@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

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: 49382

62

Neelesh A Korade

Greenhorn

Posts: 26

posted 8 years ago

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

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

Campbell Ritchie

Sheriff

Posts: 49382

62

posted 8 years ago

It needs more optimisations than that; it is cubic complexity and runs in O(

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.

*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