# Euler12

posted 4 years ago

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?

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

posted 4 years ago

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?

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?

SCJP

Visit my download page

posted 4 years ago

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.

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

Campbell Ritchie

Sheriff

Posts: 50180

79

posted 4 years ago

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.

There are an infinite number of prime numbers which have much fewer than 500 factors.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?

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

Posts: 50180

79

posted 4 years ago

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

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

posted 4 years ago

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

posted 4 years ago

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

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.

posted 4 years ago

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

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

SCJP

Visit my download page

posted 4 years ago

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

SCJP

Visit my download page

posted 4 years ago

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

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

SCJP

Visit my download page

dennis deems

Ranch Hand

Posts: 808

posted 4 years ago

So I took these hints from this topic:

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.

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

posted 4 years ago

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

Winston

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

posted 4 years ago

- 1

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)

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)

SCJP

Visit my download page

posted 4 years ago

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

my solution starts at 1(496 probably made no difference)

it only takes 5 seconds so improving it is a low priority now

SCJP

Visit my download page

Campbell Ritchie

Sheriff

Posts: 50180

79

posted 4 years ago

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

Steve

posted 4 years ago

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:

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

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

posted 4 years ago

Sweet! This is exactly what I've been doing to solve these problems!

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!