Duncan's blog

October 25, 2014

Project Euler: problem 12 (PHP) – Highly divisible triangular number

Filed under: PHP,Project Euler — duncan @ 12:24 pm
Tags:

12I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 12:

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?

Here’s my code:

<?php
$limit = 500;
$counter=1;

do {
	$currentTriangle = getTriangle($counter);

	$countFactors = getCountFactors($currentTriangle);
	
	$counter++;
} while ($countFactors <= $limit);

echo $currentTriangle;


function getTriangle($number) {
	return $number * ($number + 1) / 2;
}


function getCountFactors($number) {
	$countFactors = 0;
	$root = sqrt($number);
	
	for ($i = 1; $i <= $root; $i++) {
		if ($number % $i == 0) {
			$countFactors += 2;
		}
	}
	
	return $countFactors;
}

To begin with I was adding each factor into an array, returning that, then counting the length of the array.  However I later realised I didn’t really need to do that, I could just increment the count of factors by 2 each time.  Originally I was doing:

	for ($i = 1; $i <= sqrt($number); $i++) {
		if ($number % $i == 0)
		{	
			$factors[] = $i;
			$factors[] = $number / $i;
		}
	}

Getting rid of that array didn’t really make any improvements on speed.  However, one other amendment did; in my for loop I was calculating the square root on every iteration of the loop:

	for ($i = 1; $i <= sqrt($number); $i++) {

Moving that value into a variable prior to the for loop more than halved the execution time, from about 25 seconds(!) to about 11:

	$root = sqrt($number);
	
	for ($i = 1; $i <= $root; $i++) {

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: