File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Triangle Numbers Divisors Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Triangle Numbers Divisors" Watch "Triangle Numbers Divisors" New topic
Author

Triangle Numbers Divisors

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
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

Joined: Oct 13, 2005
Posts: 39478
    
  28
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
Sheriff

Joined: Sep 28, 2004
Posts: 18917
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19726
    
  20

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.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Sam Benry
Ranch Hand

Joined: Mar 21, 2008
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

Joined: Oct 13, 2005
Posts: 39478
    
  28
Yes, I see what you mean. I was mistaken. Sorry.
Neelesh A Korade
Greenhorn

Joined: Jun 07, 2007
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

Joined: Mar 21, 2008
Posts: 89
@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

Joined: Oct 13, 2005
Posts: 39478
    
  28
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

Joined: Mar 21, 2008
Posts: 89
http://blog.plover.com/oops/triangular-phi.html
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Triangle Numbers Divisors