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

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
JanDW
Forum Newbie
Posts: 2
Joined: Sat Oct 10, 2009 5:35 pm

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

Post 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?
User avatar
prometheuzz
Forum Regular
Posts: 779
Joined: Fri Apr 04, 2008 5:51 am

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

Post 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;
  }
}
JanDW
Forum Newbie
Posts: 2
Joined: Sat Oct 10, 2009 5:35 pm

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

Post by JanDW »

Thanks a lot for your help, this works so much faster! Seems like I'm making things too complicated for myself.
Cheers.
User avatar
prometheuzz
Forum Regular
Posts: 779
Joined: Fri Apr 04, 2008 5:51 am

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

Post by prometheuzz »

You're welcome.
Post Reply