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:

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?

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?

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 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: 41601

31

posted

0

It is also worth running from 2 to √n inclusive and looking for ≥499 divisors.

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.

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).

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.

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

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.

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

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)

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: 41601

31

posted

0

Well done

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

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.

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

posted

0

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!