wood burning stoves 2.0*
The moose likes Java in General and the fly likes Euler12 Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Euler12" Watch "Euler12" New topic
Author

Euler12

Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2


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 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?



i have an algorithm that probably works correctly(i think), but it is basically O(n * n)
it is way too slow
i need to start somewhere other than 1
500! wont work because numbers smaller than that can have 500 factors
496(the largest triangular number under 500 is a safe bet but hardly helps
the ideal starting place would be the last triangular number that cannot possibly have 500 factors
any ideas to shorten my loop?

SCJP
Visit my download page
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

It's hard to suggest improvements to your algorithm without actually seeing it.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

i want to start the outer loop at a much bigger number than 496
it takes a long time starting at 1(or 496) and many "small" numbers cannot possibly have 500 factors
i guess what i wish i knew is: what is the largest number(triangular or otherwise) that cannot possibly have over 500 factors?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:i want to start the outer loop at a much bigger number than 496
it takes a long time starting at 1(or 496) and many "small" numbers cannot possibly have 500 factors


I don't know what your loops look like.

I don't know how you're finding the factors of a given number.

I don't know how much your code takes into account about the properties of these triangular numbers and how much is brute force.

i guess what i wish i knew is: what is the largest number(triangular or otherwise) that cannot possibly have over 500 factors?


That seems to go against the spirit of the problem.

Are you making use of the fact that the sum of the the integers 1..N is N * (N + 1) / 2 ? That may or may not help the factorization.

Are you finding factors of N by trying to divide N by every integer less than N? That's definitely bad. Less than N / 2? That's no better. Less than sqrt(N)? That's better, but probably still not optimal.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
Randall Twede wrote: . . . i guess what i wish i knew is: what is the largest number(triangular or otherwise) that cannot possibly have over 500 factors?
There are an infinite number of prime numbers which have much fewer than 500 factors.

By the way, by divisors, they mean distinct divisors; 28, for example, has 3 prime factors 2 × 2 × 7. You ought to remember from your junior school maths (or by reading a previous post) that there is a quick way to calculate triangular numbers, so I am not sure your algorithm ought to run in quadratic complexity.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
It is also worth running from 2 to √n inclusive and looking for ≥499 divisors.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Jeff Verdegan wrote:
i guess what i wish i knew is: what is the largest number(triangular or otherwise) that cannot possibly have over 500 factors?


That seems to go against the spirit of the problem.


You mean that using math in advance to reduce the amount of work necessary is a bad thing? (For that particular question: there are arbitrarily large numbers that have only 2 factors -- namely prime numbers.)

Are you making use of the fact that the sum of the the integers 1..N is N * (N + 1) / 2 ? That may or may not help the factorization.


If you don't mind using some math in advance, you don't need to find the number of factors of N * (N + 1) / 2. It's sufficient to find the number of factors of N and the number of factors of N + 1 and do a little bit of arithmetic.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6



i * i < number would be better

And you'd be better off counting down instead of up, since if, for example, 12 is a factor, then you also know that all of 12s factors (2,3,4,6) are, so there's no need to test them. (But then you'd have to use Math.sqt(i) instead of i * i).
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Paul Clapham wrote:
Jeff Verdegan wrote:
i guess what i wish i knew is: what is the largest number(triangular or otherwise) that cannot possibly have over 500 factors?


That seems to go against the spirit of the problem.


You mean that using math in advance to reduce the amount of work necessary is a bad thing? (For that particular question: there are arbitrarily large numbers that have only 2 factors -- namely prime numbers.)


I mean trying to shortcut the starting point, though, I guess it would depend on what he actually does and how.

Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

thanks Campbell, i will try checking to sqrt(n) inclusive. it might be enough.

i had trouble understanding the problem.
for example the number 12 = 3 * 4
the way i understand the problem they want 1,2,3,4,6,12 so it has 6 factors
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

that helped. it takes maybe 1 minute now. now i have to go to the website and make sure the answer is correct
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

well, wrong answer. but i can take it from here.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

i * i <= number doesnt work
take 16 for example the sqrt is 4 but it also has 8 and 16 as factors
i tried changing >500 to >498 but i still get the same answer and it is still incorrect
i WILL find the answer though

i might try going back to !(i > number / 2)
and change if(factors > 500) to if(factors > 499) to account for the number itself being a factor.
if i wait long enough i might get the correct answer. then i can go to the forum for this problem and see how others solved it
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Randall Twede wrote:i * i <= number doesnt work
take 16 for example the sqrt is 4 but it also has 8 and 16 as factors

Yes, but you can make use of the fact that factors come in complementary pairs.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Dennis Deems wrote:Yes, but you can make use of the fact that factors come in complementary pairs.


Except when the number being factorized is a perfect square.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4176
    
  21

So I took these hints from this topic:

Campbell Ritchie wrote:It is also worth running from 2 to √n inclusive

"Dennis Deems" wrote:make use of the fact that factors come in complementary pairs

"Paul Clappham" wrote:Except when the number being factorized is a perfect square


Added nuggets like:
"There are at minimum 2 factors to each number"
and
"A triangle number is the triangle index + the previous triangle number"
-> meaning the 7th triangle number = 6th triangle number + 7.

I started my count at the last triangle provided as part of the problem (index = 7, value = 28), and counted up wards (incrementing the index, calculating the value).

And I modified your code a bit with this information. I got the correct answer and it tool longer to compile than to run.


Steve
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:i * i <= number doesnt work


Yes it does.

take 16 for example the sqrt is 4 but it also has 8 and 16 as factors


And when you find 1, you'll find 16, and when you find 2, you'll find 8.

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7652
    
  19

Randall Twede wrote:i might try going back to !(i > number / 2)
and change if(factors > 500) to if(factors > 499) to account for the number itself being a factor.
if i wait long enough i might get the correct answer. then i can go to the forum for this problem and see how others solved it

You may find this paper on perfect numbers a help, because it includes a proof that all even perfect numbers are triangular. I'm not sure whether that will necessarily find you the smallest triangular number that has over 500 factors (there are also pluperfect numbers; I'm just not sure if any of them are triangular or not), but it contains quite a lot of useful stuff.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

Steve beat me to it.
i solved it using what Campbell and Dennis told me.
i figured out that if sqrt(n) is a factor it is different from the other factors (in this context)
my solution takes about 5 seconds on a 2004 laptop
good enough(at least for now)
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

Winston i will try to check that out just out of curiosity.
my solution starts at 1(496 probably made no difference)
it only takes 5 seconds so improving it is a low priority now
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
Well done

And as for all those different kinds of number, it makes me all tense just thinking about them
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4176
    
  21

If you start getting to really large numbers, then there are a few things you can do to speed it up. For example, if you have a loop like this:


You can eliminate a significant portion if iterations by checking:


This adds more code plus a condition check in so it can remove 1/4 of the iterations (1/2 iterations for 1/2 factors). You can further reduce the number of iterations with more condition checking, but the payoff is reduced for each one.
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3610
    
  60

You've made me to solve my first Project Euler problem. And all that only because I believed that for large numbers, there is even faster way of obtaining number of factors:

1) Obtain prime factors. This is much faster, since you can use a list of primes (either precomputed, or created on the fly) to do division tests. After each prime factor found the remaining number is diminished, which also speeds things up greatly.

2) Compute the number of all factors which can be obtained from the list of prime factors. The good thing is you don't have to materialize the factors, which is a great time saver, you need just the number. I cheated and looked this up, though it is so clear that I feel greatly ashamed I didn't figure this out on my own. Drat!

By the way, Project Euler has told me:
You are the 59999th person to have solved this problem.

One too soon. Drat again!

Note: you can download a PDF when you solve the problem, and it turns out there is still significant speedup available to the solution I've described. Math is beautiful
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Martin Vajsar wrote:1) Obtain prime factors. This is much faster, since you can use a list of primes (either precomputed, or created on the fly) to do division tests. After each prime factor found the remaining number is diminished, which also speeds things up greatly.

2) Compute the number of all factors which can be obtained from the list of prime factors. The good thing is you don't have to materialize the factors, which is a great time saver, you need just the number. I cheated and looked this up, though it is so clear that I feel greatly ashamed I didn't figure this out on my own. Drat!


Sweet! This is exactly what I've been doing to solve these problems!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Euler12