Euler12

[Randall Twede]

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]

It's hard to suggest improvements to your algorithm without actually seeing it.

[Randall Twede]

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]

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]

	public String solve()
	{
		long number = 496;
		int factors = 1;
		int count = 1;
		
		while(true)
		{
			number = (number * (number + 1)) / 2;
			for(int i = 1; !(i > number / 2); i++)
			{
				if(number % i == 0)
				{
					factors++;
				}
			}
			if(factors > 500)
			{
				break;
			}
			count++;
			number = count;
			//System.out.println(factors);
			factors = 1;
		}
		//System.out.println(factors);
		return Long.toString(number);
	}
	
	public String getMessage()
	{
		return "What is the value of the first triangle number to have over five hundred factor?";
	}
}

[Campbell Ritchie]

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]

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

[Paul Clapham]

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]

            for(int i = 1; !(i > number / 2); 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).

[Jeff Verdegan]

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]

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]

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]

well, wrong answer. but i can take it from here.

[Randall Twede]

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]

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]

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]

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]

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]

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]

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]

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]

Well done

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

[Steve Luke]

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:

for (int i = 2; i < sqrt_of_n; i++) {
    //check if i is a factor
}

You can eliminate a significant portion if iterations by checking:

if (triangle % 2 == 0) {
  //triangle is even, check both odd and even factors
  factors += 2;

  for (int i = 3; i < sqrt_of_n; i++) {
    //check if i is a factor
  }
} else {
  //triangle is not even, so only check odd factors

  for (int i = 3; i < sqrt_of_n; i +=2) {
    //check if i is a factor
  }
}

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 Vashko]

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]

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!