Duncan's blog

December 18, 2014

Project Euler: problem 46 – Goldbach’s other conjecture

Filed under: PHP,Project Euler — duncan @ 11:57 pm
Tags: , , ,

46I’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 46:

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

This was another of those problems that I’d initially passed over, having decided it looked a bit tricky.  Then looking at it again realised it probably wasn’t too difficult.  And I turned out to be right!

A composite number is basically any positive integer that isn’t a prime number.

My logic is simply:

  • Loop through odd numbers, from 3 upwards.
  • For each number, if it’s prime, add it to an array of primes for later reference.
  • If it’s not prime, work out if it matches the conjecture:
    • Subtract the next largest prime, then examine the remainder
    • Divide the remainder by 2.  if it’s a square number then we’re meeting the conjecture.  Move onto the next odd number.
    • Otherwise keep subtracting the primes, checking the remainders.
    • If we’ve looped through all the primes then we must have reached a number that doesn’t meet the conjecture.

This runs in about 40ms:

$primes = [2];

$i= 1;

while (true) {
	$i+= 2;

	if (isPrime($i)) {
		$primes[] = $i;
	} else {
		for($j = count($primes)-1; $j > 0; $j--) {
			$remainder  = $i - $primes[$j];
			$remainder = $remainder / 2;
			$root = sqrt($remainder);
			if ((int) $root == $root) {
				continue 2;
		echo $i;

function isPrime($x)
	$root = sqrt($x);
	for ($i = 3; $i <= $root; $i += 2) {
		if ($x % $i == 0) {
			return false;
	return true;

I’m using a modified version of my original isPrime function, just because I know I don’t need to check for even numbers.

The loop backwards through the primes was maybe a bit of overkill; using a simple foreach loop through the primes in ascending order took more like 100ms.

What else… I check if a square root is the same as when it’s cast to an integer (not sure this is the best approach).  Then use continue 2; to get out of our inner-most loop and move onto the next value in our parent loop.

December 14, 2014

Project Euler: problem 33 (PHP) – Digit cancelling fractions

Filed under: PHP,Project Euler — duncan @ 10:54 pm
Tags: ,

Picture by jessicakelly

I’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 33:

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

It took me a couple of tries to get this, I think as the question doesn’t give enough details about what the rules are for anomalous fraction cancellation.

Supposing we say our fractions are of the form ab / cd.  Initially I was checking each of the following:

  • a / c = ab / cd
  • a / d = ab / cd
  • b / c = ab / cd
  • b / d = ab / cd

i.e. each possible combination of the first and second numerator and denominator digits.

Then I realised I could omit two of these, as we didn’t want to look at those cases where it’s the first numerator digit divided by the first denominator digit, or the second numerator digit divided by the second denominator digit.  Reducing what I was checking down to:

  • a / d = ab / cd
  • b / c = ab / cd

So I was now just looking at the first numerator over the second denominator, and the second numerator over the first denominator.  However this was still giving me too much possible fractions.  Further reading illustrated that the example given, 49 / 98, where the second numerator digit and the first denomator digit are cancelled out, is the rule for all cases.  Reducing what I was checking to just:

  • a / d = ab / cd

The question also doesn’t really explain what else you can ignore.  Firstly if either digit is zero.  Secondly, the trivial examples include where a = b and c = d, e.g. 11 / 22.

And finally, I thought you could look at any values for ab and cd, e.g. I’d got 16 / 96 = 1 / 6.  But this meant I’d still got more than four ‘matching’ fractions.  What the question failed to mention is that the digits being cancelled out had to be identical, so really what I was checking was changed to:

  • a / c = ab / bc

Once I’d got all that cleared up, it was easy.

$product = 1;

for ($numerator = 10; $numerator <= 99; $numerator++) {
	for ($denominator = $numerator+1; $denominator <= 99; $denominator++) {
		$fraction = $numerator / $denominator;
		$numeratorAsString = (string)$numerator;
		$denominatorAsString = (string)$denominator;
		if (
			!isTrivial($numeratorAsString, $denominatorAsString) && 
			$numeratorAsString[1] == $denominatorAsString[0] && 
			$numeratorAsString[0] / $denominatorAsString[1] == $fraction
		) {
			$product *= $fraction;

function isTrivial($numerator, $denominator) {
	if ($denominator[1] == 0) {
		return true;
	if ($numerator[0] == $numerator[1]) {
		return true;
	return false;

echo $product;

I cast my numerators and denominators to strings, enabling me to then reference the digits within each using array notation.

Some useful links:

December 10, 2014

Project Euler: problem 27 (PHP) – Quadratic primes

Filed under: PHP,Project Euler — duncan @ 8:00 am
Tags: , ,

Photo by Ianqui Doodle

I’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 27:

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000
where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

This was another puzzle I’d ignored previously, then looked at it again and realised it wasn’t that hard after all.  First time I’ve really done anything with quadratics since school probably!

include 'isPrime.php';

$maxPrimes = 0;
$maxCoefficients = [];

calculatePrimes(1, 1);
calculatePrimes(1, -1);
calculatePrimes(-1, 1);
calculatePrimes(-1, -1);

function calculatePrimes($incrementA, $incrementB) {
	global $maxPrimes;
	$a = 0; 
	while (abs($a) < 1000) {
		$b = 0;
		while (abs($b) < 1000) {
			$n = 0;

			while (true) {
				$q = ($n * $n) + ($n * $a) + $b;
				if (!isPrime($q)) {
					if ($n > $maxPrimes) {
						$maxPrimes = $n;
						setMaxCoefficients($a, $b);
			$b+= $incrementB;
		$a+= $incrementA;

function setMaxCoefficients($a, $b) {
	global $maxCoefficients;
	$maxCoefficients = [$a, $b];

echo $maxCoefficients[0] * $maxCoefficients[1];

So I’ve wrapped up most of the code into one function, which I call four times.  Each time I’m either adding or subtracting 1 from each of the two coefficients.  Then there’s nested loops so we’re going from zero to +/- 999 for both coefficients.  Within that we loop again, incrementing $n until our quadratic equation doesn’t return a prime number.  At that point, we check if the value of $n is more than the previous maximum number of primes.  And if it is, I update a global array with those coefficients.

After we finish looping, I then calculate the production from those stored coefficients.  Simple, but not particularly fast.

December 3, 2014

Project Euler: problem 32 (PHP) – Pandigital products

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

Photo by Lars Dahlin

I’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 32:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

This if the first one of these Project Euler puzzles I’ve completed in the last month.  I’d been sidelined by a much harder one, given up on it for now, and tried this instead for the first time.  It wasn’t too hard either; I’m not sure why I hadn’t attempted it previously.

$sums = [];

for ($i = 1; $i < 9; $i++) {
	for ($j = 1234; $j < 9876; $j++) {
		getPandigitalProduct($i, $j, $sums);

for ($i = 12; $i < 98; $i++) {
	for ($j = 123; $j < 987; $j++) {
		getPandigitalProduct($i, $j, $sums);

echo array_sum($sums);

function getPandigitalProduct($multiplicand, $multiplier, &$sums) {
	$product = $multiplicand * $multiplier;
	$number =  $multiplicand . $multiplier . $product;
	if (isPandigital($number)) {
		$sums[$product] = $product;

function isPandigital($number) {
	$length = strlen($number);
	if ($length != 9) {
		return false;
	for ($i = 1; $i <= $length; $i++) {
		if (strpos($number, (string)$i) === false) {
			return false;
	return true;

Not the cleanest code, but it’s reasonably fast.  In the isPandigital function I just loop from 1 to 9, checking that each of those digits is present in the number (after checking that it’s 9 digits long of course).

The important thing to understand is why I’m doing two separate nested loops.  The first one is for getting 9-digit identities which look like:

1 * 2345 = 6789

The second one is for getting identities which look like:

12 * 345 = 6789

Initially I had it in one set of nested loops, like:

for ($i = 1; $i < 99; $i++) {
	for ($j = 1; $j < 9999; $j++) {

However that made 979804 iterations!  Doing it this way there’s a total of 143440 iterations (still way too many of course).

Also note I’m explicitly passing the $sums array by reference by specifying the ampersand before the argument in the function declaration.

What else… I had to cast the value of $i to a string before being able to use it succesfully with the strpos function.

November 2, 2014

Project Euler: problem 95 (PHP) – Amicable chains

Filed under: PHP,Project Euler — duncan @ 3:50 pm

bike chainI’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 95:

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

This puzzle took me a while to get right.  The question doesn’t really give you enough details I think, so it pays to do a bit of research into what perfect numbers, amicable pairs and amicable chains are.  Perfect numbers are an amicable chain with length = 1, and amicable pairs are amicable chains with length = 2.

Continuously adding up the divisors of numbers (the factors of a number apart from the number itself) is called the Aliquot sequence.  Eventually you should either end up running into an amicable chain, or you’ll reach a prime number (i.e. its divisors = 1, and you can’t go any further).  However there are theoretically numbers who’s Aliquot sequence never terminates.  I guess that’s why this question makes sure we don’t have any individual numbers over 1 million.

One thing that’s useful to know, the question doesn’t give you a clue on when you’ll know you’ve reached the longest amicable chain; I assumed it might be into the hundreds.  Fortunately the Wikipedia article on sociable numbers reveals that the longest one is a chain of only 28 numbers in length.


$start = microtime(true);

$number = 1;
$limit = 1000000;
$amicableChains = []; 
$length = 0;
$maxLength = 28;

while ($length < $maxLength) {
	$chain = [];
	$currentNumber = $number;

	while (true) {
		$divisors = getDivisors($currentNumber);
		$currentNumber = array_sum($divisors);
		if (array_key_exists($currentNumber, $amicableChains)) {
			$amicableChains[$number] = $amicableChains[$currentNumber];
		if ($currentNumber == 1) {
		// break out if we're over a certain length of number
		if ($currentNumber > $limit) {
		if (in_array($currentNumber, $chain)) {
			$key = array_search($currentNumber, $chain);
			$amicableChains[$number] = array_slice($chain, $key);
			$length = count($amicableChains[$number]);
		$chain[] = $currentNumber;

uasort($amicableChains, function($a, $b) {
	return count($a) > count($b);

echo min(end($amicableChains));

$end = microtime(true);
printf("<br>Execution time: %dms", ($end - $start) * 1000);

function getDivisors($number) {
	$factors = [1];
	$root = sqrt($number);
	for ($i = 2; $i <= $root; $i++)
		if ($number % $i == 0)
		{	// it's a factor
			$factor1 = $i;
			$factor2 = $number / $i;
			$factors[] = $factor1;
			if ($factor1 != $factor2) {
				$factors[] = $factor2;
	return $factors;

So we loop until we’ve reached a chain with a length of 28+.

Within that loop we have an inner loop, where we calculate the sum of the divisors.  We break out of that inner loop if:

  • we reach a value we already have the amicable chain for
  • the sum of divisors reaches 1
  • we have a value that exceeds one million
  • we get to a value that we already have in the current chain, i.e. we’ve reached a new amicable chain

Initially I had some logic in that inner loop to break out if the current number equalled the previous number, i.e. we had reached a perfect number, an amicable chain of length = 1.  However that wasn’t really required, as the final if statement further down covered it anyway, and it didn’t really slow things down to just use that.

Once we get an amicable chain, I store that chain keyed on the number we’re currently looping over.  N.B this number may not be part of the chain itself.  For instance the divisors of 562 are 1, 2 and 281.  The sum of these is 284.  We already know that 284 is part of the amicable chain 220 → 284.  So the aliquot sequence for 562 is 220 → 284.

Once we’ve reached our limit of a chain with length of 28, I then use the uasort() function to have a user-defined function which sorts my array of amicable chains based on the length of each array within it.  Then I use end() to get the last of those amicable chains, i.e. the longest.  And min() to get the smallest value within that chain.

Job done, running time about 1.5 seconds on average.


October 29, 2014

Project Euler: problem 99 (PHP) – Largest exponential

Filed under: PHP,Project Euler — duncan @ 7:00 am

99I’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 99:

Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187.

However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt, a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

Interesting, sounds quite difficult.  At first I thought I could use the BC Math functions which have proven so useful in many of the previous puzzles and “support numbers of any size and precision”.  However they didn’t seem to work; according to this StackExchange question they “can handle numbers greater than 2^1000000 (which is 301,030+ digits)“. We’re dealing with numbers here that are ten-fold of that!  So I used the GMP functions instead, which “allow you to work with arbitrary-length integers”.

$pairs = file('p099_base_exp.txt');

$max = 0;

foreach($pairs as $key=>$pair) {
	$numbers = explode(",", $pair);
	$base = $numbers[0];
	$exponent = $numbers[1];

	$power = gmp_pow($base, intval($exponent));
	if (gmp_cmp($power, $max) > 0) {
		$max = $power;
		$lineNumber = $key;

echo $lineNumber+1;

I read the file in using file(), turning each line into an array element.  I then loop over those 1000 array elements, using explode() to split each line into its base and exponent parts.

Then I use the gmp_pow() function; however when I tried it initially simply using gmp_pow($base, $exponent) it threw up this error: “A non well formed numeric value encountered“.  It expects $exponent to be an integer, which to all intents and purposes, it seems to be.  However I had to explicitly cast it to an integer, using either intval($exponent) or (int)$exponent – both seemed to work.

Initially I thought I had to use a GMP number for the base, so was using gmp_init() to create one from $base.  However in the end that didn’t seem to be necessary.  So the gmp_pow() function is fussy about what kind of value it gets for the exponenent, but less-so for the base… curious.

After working out the power, I then compare it the maximum power so far, using gmp_cmp().  Each time I get a new maximum value I keep track of which line number that belongs to.  At the end when I output that I increment it by 1, due to PHP arrays being zero-indexed.

This is very slow code, taking close to 5 minutes!

PS: to get the GMP functions to work on my Windows environment I had to uncomment this line in php.ini:


October 28, 2014

Project Euler: problem 74 (PHP) – Digit factorial chains

Filed under: PHP,Project Euler — duncan @ 8:00 am

74I’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 74:

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?


$countChains = 0;
$limit = 1000000;
$terms = 60;

$factorials = getFactorials();

foreach (range(1, $limit) as $number) {
	$currentNumber = $number;
	$count = 0;
	$chain = [$currentNumber];
	while (true) {
		$sum = 0;

		$digits = str_split($currentNumber);
		foreach($digits as $digit) {
			$sum += $factorials[$digit];
		$currentNumber = $sum;
		if (in_array($currentNumber, $chain)) {
		$chain[] = $sum;
	if ($count == $terms) {
echo $countChains;

function getFactorials() {
	$factorials = [];
	for ($i = 0; $i <= 9; $i++) {
		$factorials[$i] = factorial($i);
	return $factorials;

function factorial($x) {
	$factorial = 1;
	for ($i = $x; $i > 1; $i--) {
		$factorial *= $i;
	return $factorial;

Re-using the approach here from Problem 34, where I first calculated the factorials for the digits 0..9.

Then I loop from one to a million.  I create an array which initially contains the current number.  I then loop over the digits of that number, adding up the factorials of each digit.

If that value is already in our array, then we need to break out of the inner loop, as we’ve reached a repeating term.

Otherwise, add that into the array, and keep on adding up the factorial values of that new value, ad infinitum (well, ad 60 really).

After finishing with our inner loop, i.e. the point at which we’ve reached a repeating term, I check if the length of that chain was 60.

This is pretty slow stuff, taking over 2 minutes to execute!

October 27, 2014

Project Euler: problem 112 (PHP) – Bouncy numbers

Filed under: PHP,Project Euler — duncan @ 8:00 am

Photo by Leo Reynolds

I’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 112:

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.


$proportion = 0;
$bouncies = 0;
$limit = 99;
$number = 1;

while (true) {
	if (isBouncy($number)) {
	$proportion = $bouncies / $number * 100;
	if ($proportion == $limit) {
		echo $number;

function isBouncy($number) {
	return !(isIncreasing($number) || isDecreasing($number));

function isIncreasing($number) {
	$digits = str_split($number);
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
		if($digits[$i] < $digits[$i-1]) {
			return false;
	return true;

function isDecreasing($number) {
	$digits = str_split($number);
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
		if($digits[$i] > $digits[$i-1]) {
			return false;
	return true;

Looping until I reach the 99% proportion.  For each number, work out if it’s bouncy.  Keep track of how many bouncy numbers we have, continually calculating the proportion that are.  The isBouncy function just being a wrapper to find out which numbers are neither increasing nor decreasing.  Those functions looping over all the digits of the number, comparing each digit to the previous one.

There’s obvious duplication between the isIncreasing and isDecreasing functions.  Refactoring this to reduce that duplication:

function isBouncy($number) {
	$digits = str_split($number);
	$isIncreasing = false;
	$isDecreasing = false;
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
 		if($digits[$i] > $digits[$i-1]) {
			$isIncreasing = true;
		} elseif ($digits[$i] < $digits[$i-1]) {
			$isDecreasing = true;
		if ($isIncreasing && $isDecreasing) {
			return true;
	return false;

Doing this reduced execution time from about 14 seconds to more like 8.8.

October 26, 2014

Project Euler: problem 80 (PHP) – Square root digital expansion

Filed under: PHP,Project Euler — duncan @ 11:41 am
Tags: ,

80I’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 80:

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

So this Euler puzzle has only been solved by a little over 10,000 people at the current point, a relatively low number, from which I surmise this is conceivably the hardest puzzle I’ve solved.  In reality it wasn’t that hard however, thanks to PHP’s BC Maths functions.

$sum = 0;

for ($number = 1; $number <= 100; $number++) {
	$root = bcsqrt($number, 99);
	if ($root != round($root)) {
		$decimal = explode(".", $root);
		$sum += $decimal[0];
		$sum += array_sum(str_split($decimal[1]));

echo $sum;

Using bcsqrt() to calculate the square root of every number from 1 to 100, and I’ve specified 99 as the scale parameter, for how many digits after the decimal point I want.

I’m still not having any luck with the is_int() function, so comparing the value to its integer version using round() to see if we’re dealing with integers or irrational numbers.  Initially I didn’t think I would need to do this, as things like bcsqrt(4, 99) would return 2.000…  so adding all those zeroes wouldn’t affect my total.  However bcsqrt(1, 99) just returns 1, not 1.000… which caused an error further down in the code when using explode(), as there wasn’t any decimal point in the value.

I then turn the number into an array using explode(), splitting it on the decimal point.  I add the integer part.  Then I use str_split() to convert decimals like 4142… into arrays like [4, 1, 4, 2, …].  And then array_sum() to total up all those digits.  If we were dealing with numbers any greater than 100 then I’d need to do the same with the integer value, but otherwise I know we’re never going to have values with the integer part more than 1 digit long.

Initially I thought when it said the digital sum of the first one hundred decimal digits that it meant the first 100 digits after the decimal point.  e.g. for the square root of 2 (1.4142…) it would be 4 + 1 + 4 + 2… etc.  However I wasn’t getting the right answer.  Comparing the value I was getting for adding up the digits of the square root of 2  with the answer they’d given for that (475), I was able to see where I’d gone wrong.  They really meant just the first 100 digits of the value, including the integer part, e.g. 1 + 4 + 1 + 4 + 2… etc.

So to cater for that I reduced the scale on the bcsqrt() from 100 to 99 and also added the integer part of each square root.

October 25, 2014

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

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

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:

$limit = 500;

do {
	$currentTriangle = getTriangle($counter);

	$countFactors = getCountFactors($currentTriangle);
} 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++) {
Next Page »

Create a free website or blog at WordPress.com.