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:

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 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++) {

October 23, 2014

Project Euler: problem 39 (PHP) – Integer right triangles

Filed under: PHP,Project Euler — duncan @ 8:00 am
Image from page 208 of "The California fruits and how to grow them; a manual of methods which have yielded greatest success, with the lists of varieties best adapted to the different districts of the state" (1912)

Photo courtesy of Internet Archive Book Images

This is another Project Euler puzzle I hadn’t tried before.  I’m doing these  as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 39:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Here’s my code, I’m not sure it’s particularly efficient, taking a brute force approach to working out all the hypotenuses for right-angled triangles with sides adding up to 1000.

<?php
$solutions = [];
$limit = 1000;
	
for ($adjacent = 1; $adjacent <= $limit; $adjacent++) {
	for ($opposite = 1; $opposite <= $limit; $opposite++) {
		$hypotenuse = sqrt(pow($adjacent, 2) + pow($opposite, 2));
		
		if ($hypotenuse != round($hypotenuse)) {
			continue;
		}
		
		$perimiter = $hypotenuse + $adjacent + $opposite;
		
		if ($perimiter > $limit) {
			break;
		}
		
		if (isset($solutions[$perimiter])) {
			$solutions[$perimiter]++;
		} else {
			$solutions[$perimiter] = 1;
		}
	}
}

arsort($solutions, SORT_NUMERIC);

echo key($solutions);

I found I was able to slightly optimise the code post-completion by amending:

for ($adjacent = 1; $adjacent <= $limit; $adjacent++) {
	for ($opposite = 1; $opposite <= $limit; $opposite++) {

to:

for ($adjacent = 1; $adjacent <= $limit/2; $adjacent++) {
	for ($opposite = 1; $opposite <= $limit/2; $opposite++) {

… but this was just through trial-and-error without any real thought as to why exactly. Obviously I didn’t need to loop all the way up to the limit for the length of either individual side. In fact I could amend the outer loop to only go up to $limit/3 although that was more luck than anything; for the test limit of 120 that didn’t work.

I only wanted to work with values where the hypotenuse was an integer.  For some reason the is_int() and is_float() functions didn’t seem to work for me, so I had to use round() to check the value was identical to its integer component.

I then increment the count of how many solutions there are for this length of perimiter.  After the loop I use arsort() to reverse-sort on value (keeping the associated keys), and key() to output the value of the first element of the array.

Make sure not to confuse arsort with the multitude of other functions that sort arrays, including:

  • sortSort an array

  • rsortSort an array in reverse order

  • asortSort an array and maintain index association

  • arsortSort an array in reverse order and maintain index association

  • ksortSort an array by key

  • krsortSort an array by key in reverse order

  • natsortSort an array using a “natural order” algorithm

  • natcasesortSort an array using a case insensitive “natural order” algorithm

  • array_multisortSort multiple or multi-dimensional arrays

  • usortSort an array by values using a user-defined comparison function

  • uksortSort an array by keys using a user-defined comparison function

  • uasortSort an array with a user-defined comparison function and maintain index association

Phew!

October 22, 2014

Project Euler: problem 35 (PHP) – Circular primes

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

Punch meI ignored this Project Euler puzzle first time round I tried doing them, 5-6 years ago, with ColdFusion and Python.  Looking at it again recently I thought I could tackle it with PHP.  I’m doing these  as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 35:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

It took me a little while to get close to the answer, and I know this code isn’t the most efficient, but it works:

<?php
require 'isPrime.php';

$primes = [2 => 1];
$limit = 1000000;
$circulars = 1;
$arrCirculars = array('2' => true);

function getExcludedDigits($value) {
	return $value % 2 == 0 && $value != 5;
}

for ($i = 3; $i < $limit; $i+=2) {
	$isCircular = false;
	$rotatedDigits = str_split($i);
	
	if (count(array_filter($rotatedDigits, 'getExcludedDigits')) == 0) {
		for ($j = 1; $j <= strlen($i); $j++) {
			array_push($rotatedDigits, array_shift($rotatedDigits));
			$rotatedNumber = implode($rotatedDigits);

			// if this number's already in our primes[], move onto the next iteration
			if (array_key_exists($rotatedNumber, $primes)) {
				continue;
			}
			
			if (!isPrime($rotatedNumber)) {
				$isCircular = false;
				break;
			}
			
			$isCircular = true;
			$primes[$rotatedNumber] = true;
		}
		
		if ($isCircular) {
			if (substr_count($rotatedNumber, substr($rotatedNumber, 0, 1)) == strlen($rotatedNumber)) {
				$circulars++;
			} else {
				$circulars += strlen($rotatedNumber);
			}
			$arrCirculars[$i] = true;	
		}
	}
}

echo $circulars;

Re-using my isPrime function from puzzle 3.

One thing you’ll quickly realise is that we don’t have to calculate if every number is prime.  For instance early on in the loop you get 1951, which is a prime number.  Shifting the first number off there and sticking it on the end, you get 9511, which is also prime.  And doing it again, you get 5119, which is prime too.  However on its fourth iteration you have 1195, which is divisible by 5 and therefore not prime.  However rather than calculate if any of those four rotations of those digits would be prime, you can save time by excluding it as soon as you see there’s a 5 in there.  Similarly with numbers containing any even digits.

During the loop, I store every prime number to an array.  If it’s already in the array, then I know I don’t need to do it again.

At the end of the inner for loop, I increment my counter by the length of the number I’ve currently been looking at.  e.g. if I was on 197, which is prime, and its rotations 971 and 719 are also prime, I simply increment by 3.  I make a special exception for numbers like 11 where all the digits are the same, to make sure I don’t double-count it.

October 21, 2014

Project Euler problem 58 (PHP) – Spiral primes

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

AmmoniteI previously blogged about this Project Euler puzzle over 5 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 58:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Code:

<?php
require 'isPrime.php';

$numPrimes = 0;
$spiralLength = 1;
$number = 1;
$increment = 2;
$ratio = 100;

while ($ratio > 10) {
	$spiralLength += 2;

	// add our increment 4 times, calculating each time if it's prime
	for ($corner = 1; $corner <= 4; $corner++) {
		$number += $increment;

		// the 4th corner is never prime
		if ($corner < 4 && isPrime($number)) {
			$numPrimes++;
		}
	}
	
	$ratio = $numPrimes / ((2 * $spiralLength) - 1) * 100;
	
	$increment += 2;
}

echo $spiralLength;

Re-using the isPrime function from Problem 3.

Looping until we fall beneath a 10% ratio, adding up the numbers of primes along the corners of the spiral and calculating that amount as a ratio of the current length of the spiral’s side.

October 20, 2014

Project Euler problem 56 (PHP) – Powerful digit sum

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

NumbersI previously blogged about this Project Euler puzzle over 5 years ago, using Python.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 56:

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

Code:

<?php
$maxsum = 0;
$limit = 99;

foreach (range(1, $limit) as $base) {
    foreach (range(1, $limit) as $exponent) {
        $power = bcpow($base, $exponent);
	$total = 0;

	for ($position = 0; $position < strlen($power); $position++) {
		$total += substr($power, $position, 1);
	}

	$maxsum = max($maxsum, $total);
    }
}

echo $maxsum;

Looping 1..99 and again in an inner loop for calculating the powers.  Using the BC Math function bcpow() to do the calculation.  Then looping over those digits, adding them up, and storing the maximum value of that sum of digits.

October 19, 2014

Project Euler: problem 55 (PHP) – Lychrel numbers

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

747I previously blogged about this Project Euler puzzle over 5 years ago, using Coldfusion and Python.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 55:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,

1292 + 2921 = 4213

4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

Phew, quite a lengthy question. Here’s my code:

<?php
$countLychrels = 0;
$limit = 9999;
$maxIterations = 50;

function isPalindrome($number) {
	return $number == strrev($number);
}

function isLychrel($iterations) {
	global $maxIterations;
	return $iterations >= $maxIterations;
}

foreach (range(1, $limit) as $currentNumber) {
	$number = $currentNumber;

	foreach (range(1, $maxIterations) as $iteration) {
		$sum = $number + strrev($number);

		if (isPalindrome($sum)) {
			break;
		}
		
		$number = $sum;
	}
	
	if (isLychrel($iteration)) {
	      $countLychrels++;
	}
}
              
echo $countLychrels;

Looping from 1 to ten thousand.  For each iteration  of that loop, looping again up to fifty times, adding the number to its reverse.  If we find a palindrome at any point, it’s not a Lychrel number.  Otherwise, if we’ve looped as much as 50 times, then it must be a Lychrel.

October 18, 2014

Project Euler: problem 53 (PHP) – Combinatoric selections

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

I previously blogged about this Project Euler puzzle nearly 6 years ago, using Python.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 53:

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,
nCr = n! / (r!(n-r)!)
where r <= n, n! = n*(n-1)*…*3*2*1, and 0! = 1.


It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of nCr, for 1 <= n <= 100, are greater than one-million?

Code:

<?php
$values = 0;

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

function calc($n, $r) {
    return  factorial($n) / (factorial($r) * factorial($n-$r));
}

foreach (range(1,100) as $i) {
    foreach (range(1, $i) as $j) {
        if (calc($i, $j) > 1000000) {
            $values++;
	}
    }
}

echo $values;

One key difference here from how I did it in Python is I previously used the range() function in my factorial function.  Calling that function with ($n – $r) means that sometimes we’re calling factorial(0).   This means that we then call range(1,0), which in Python returns an empty list.  However in PHP this returns an array like this, even if I specify step=+1 :

array(2) {
    [0]=>int(1)
    [1]=>int(0)
}

So I would then have had to do an additional check that I’m not trying to calculate factorial(0), which slowed the code right down.  However I was able to re-use the factorial function from Problem 34, looping down from $x to 1, instead of doing a foreach loop over the array returned by range().  Doing so kept the code pretty quick.

October 17, 2014

Project Euler: problem 52 (PHP) – Permuted multiples

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

I previously completed this Project Euler puzzle about 6 years ago, using ColdFusion, although I never blogged about it at the time.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 52:

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Here’s my code, taking basically the same approach as I did with the ColdFusion, although I think this executes much quicker:

<?php
$smallestInteger = 1;

while (true) {
	$identicalDigits = true;
	$originalDigits = str_split($smallestInteger);

	foreach (range(2,6) as $multiplier) {
		// work out the multiples of x 
		$multiple = $smallestInteger * $multiplier;
				
		$newDigits = str_split($multiple);

		// compare this array to the previous one 
		if (count(array_diff($newDigits, $originalDigits)) != 0) {
			$identicalDigits = false;
			break;
		}
	}
	
	// did we get out of the inner loop with two identical arrays? 
	if ($identicalDigits) {
		break;
	}
	
	$smallestInteger++;	
}

echo $smallestInteger;

So I loop until finding the integer where the digits in x, 2x, 3x, 4x, 5x and 6x are identical.  I get the multiple of the number I’m currently looping over, turn its digits into an array.  I then have an inner loop from 2 to 6, checking if the digits of each multiple of my current number are identical to that number’s digits.

October 16, 2014

Project Euler: problem 49 (PHP) – Prime permutations

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

I previously blogged about this Project Euler puzzle nearly 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 49:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Code:

<?php
require 'isPrime.php';

$end = 9999 - (3330 * 2);

function sameDigits($x, $y)
{
	$i = 0; 
	$arrX = str_split($x);
	$arrY = str_split($y);
	
	sort($arrX, SORT_NUMERIC);
	sort($arrY, SORT_NUMERIC);
	
	return count(array_diff($arrX, $arrY)) === 0;
}

for ($i = 1489; $i <= $end; $i += 2) {
	$num2 = $i + 3330;
	$num3 = $num2 + 3330;
	
	if 	(
			sameDigits($i, $num2) 
		&& 	sameDigits($i, $num3) 
		&& 	isPrime($i)
		&& 	isPrime($num2)
		&& 	isPrime($num3)
	) {
		echo $i . $num2 . $num3;
		break;
	}
}


Re-using my isPrime function from Problem 3.

Previously in ColdFusion I had an overly-complicated function which took two numbers as arguments, looped over them inserting them to arrays, sorted the arrays, then looped over the arrays to work out if all the digits were identical.  In PHP I can simply use str_split() to convert the numbers into arrays, then array_diff() to compare the two arrays.  I’ve used count() to check that the ‘diff’ array returned by array_diff is empty, quite probably there’s more efficient ways to do this.

Yet another example of PHP’s inconsistencies; some array functions like array_diff are prefixed with ‘array_’, some like sort are not, with no obvious rhyme or reason behind it that I can discern.

October 15, 2014

Project Euler: problem 48 (PHP) – Self powers

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

I previously blogged about this Project Euler puzzle nearly 6 years ago, using Python.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 48:

The series, 11 + 22 + 33 + … + 1010 = 10405071317.

Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.

Code:

<?php
$limit = 1000;
$sum = 0;

foreach (range(1, $limit) as $i) {
	$sum = bcadd($sum, bcpow($i, $i));
}

echo substr($sum, -10);

Short question, short answer.  Using the BC Math functions due to the size of the numbers involved… not quite as fast to spit out the answer as it was with Python though.  Here using PHP’s substr() function which seems more useful than ColdFusion’s Mid() as by specifying a negative number it allows us to start 10 characters from the end of the string… and the third parameter is optional for the length required.

Next Page »

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 537 other followers