Page 1 of 1

projecteuler.net problem #12: triangle # with 500+ divisors

Posted: Sat Oct 10, 2009 6:01 pm
by JanDW
I’m trying to learn some PHP so I embarked on Project Euler. So far it has been something in between jolly good fun and having tendencies to gobble up a live goat out of frustration.

I’ve worked my way up to problem 12, and the solution I’ve created is way too slow (beyond waiting for it to finish slow), so I was hoping some more advanced coders could help me clean and speed it up: here’s the code on pastie.org the

Code: Select all

while ($delers < 500) {
in the pastie should be

Code: Select all

while ($delers < 501) {
This is the problem statement:
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?

Re: projecteuler.net problem #12: triangle # with 500+ divisors

Posted: Sun Oct 11, 2009 4:53 pm
by prometheuzz
I'm not too fluent in PHP and therefor found your code a bit hard to read.
The trick in solving this one lies in the fact that you only need to loop to sqrt(N) to count all dividers of a number N. Whenever you find a divider, just increase the counter by 2.
Here's a small demo:

Code: Select all

function number_of_dividers($n) {
  $dividers = 0;
  $stop = sqrt($n);
  for($i = 1; $i < $stop; $i++) {
    if($n%$i == 0) {
      $dividers += 2;
    }
  }
  return $dividers;
}
 
function triangle_number($n) {
  return ($n * ($n + 1)) / 2;
}
 
$max_dividers = 500;
for($n = 1; ; $n++) {
  $triangle_num = triangle_number($n);
  $dividers = number_of_dividers($triangle_num);
  if($dividers >= $max_dividers) {
    echo "$triangle_num has $dividers dividers!\n";
    break;
  }
}

Re: projecteuler.net problem #12: triangle # with 500+ divisors

Posted: Mon Oct 12, 2009 10:34 am
by JanDW
Thanks a lot for your help, this works so much faster! Seems like I'm making things too complicated for myself.
Cheers.

Re: projecteuler.net problem #12: triangle # with 500+ divisors

Posted: Tue Oct 13, 2009 12:51 am
by prometheuzz
You're welcome.