• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Triangle Numbers Divisors

 
Sam Benry
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 48382
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20882
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20494
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@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: 48382
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, I see what you mean. I was mistaken. Sorry.
 
Neelesh A Korade
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@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
Sheriff
Posts: 48382
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic