This week's book giveaway is in the Clojure forum.
We're giving away four copies of Clojure in Action and have Amit Rathore and Francis Avila on-line!
See this thread for details.
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Euler12

 
Randall Twede
Ranch Hand
Posts: 4353
2
Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's hard to suggest improvements to your algorithm without actually seeing it.
 
Randall Twede
Ranch Hand
Posts: 4353
2
Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4353
2
Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Campbell Ritchie
Sheriff
Pie
Posts: 47232
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 47232
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It is also worth running from 2 to √n inclusive and looking for ≥499 divisors.
 
Paul Clapham
Sheriff
Pie
Posts: 20177
25
MySQL Database
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4353
2
Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4353
2
Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4353
2
Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
well, wrong answer. but i can take it from here.
 
Randall Twede
Ranch Hand
Posts: 4353
2
Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 808
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 20177
25
MySQL Database
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 4181
21
IntelliJ IDE Java Python
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9472
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Randall Twede
Ranch Hand
Posts: 4353
2
Java
  • 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4353
2
Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 47232
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well done

And as for all those different kinds of number, it makes me all tense just thinking about them
 
Steve Luke
Bartender
Pie
Posts: 4181
21
IntelliJ IDE Java Python
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 3747
62
Chrome Netbeans IDE Oracle
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 808
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic