• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Triangle Numbers Divisors

 
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?

 
Marshal
Posts: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, I see what you mean. I was mistaken. Sorry.
 
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
http://blog.plover.com/oops/triangular-phi.html
reply
    Bookmark Topic Watch Topic
  • New Topic