Duncan's blog

October 22, 2014

Project Euler: problem 35 (PHP) – Circular primes

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

I 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

I 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

I 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

I 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.

October 14, 2014

Project Euler: problem 45 (PHP) – Triangular, pentagonal, and hexagonal

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 45:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal Pn=n(3n1)/2 1, 5, 12, 22, 35, …
Hexagonal Hn=n(2n1) 1, 6, 15, 28, 45, …

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Code:

<?php
function isTriangle($x) {
	$number = (sqrt((8 * $x) + 1) - 1) / 2;
	
	return isInteger($number);
}

function isPentagonal($x) {
	$number = (sqrt((24 * $x) + 1) + 1) / 6;
	
	return isNaturalNumber($number);
}

function isHexagonal($x) {
	$number = (sqrt((8 * $x) + 1) + 1) / 4;
	
	return isInteger($number);
}

function isInteger($number) {
	return $number == round($number);
}

function isNaturalNumber($number) {
	return isInteger($number) && $number > 0;
}

$number = 1;
$add = 2;

while (true) {
	$number += $add;
	$add++;
	if ($number > 40755 && isTriangle($number) && isPentagonal($number) && isHexagonal($number)) {
		break;
	}
}

echo $number;

Nothing too fancy, basically the same as I had previously with CFML.  On the previous problem I used intval() to check if a number was an integer.  Here I’m using round() to do the same thing.  I tried using is_int(), however that just seemed to time out.

October 13, 2014

Project Euler: problem 44 (PHP) – Pentagon numbers

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

I 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 44:

Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

Code:

<?php
function getPentagonal($x) {
	return $x * (3 * $x - 1) / 2;
}

function isPentagonal($x) {
	$n = (sqrt((24 * $x) + 1) + 1) / 6;

	return $n == intval($n) && $n > 0;
}
        
$i = 0;
$pentagonals = [];

while (true) {
	$i++;
	$p = getPentagonal($i);

	foreach ($pentagonals as $j) {
		$diff = abs($p - $j);
		
		if (isPentagonal($diff)) {
			$intSum = $p + $j;
			
			if (isPentagonal($intSum)) {
				echo "solution:" . $diff;
				break 2;
			}
		}
	}

	$pentagonals[] = $p;
}

A fraction simpler code than with Python.  Similar to Problem 45, you’d assume PHP’s is_int() function would be useful at working out whether a value is an integer.  However it just seems to time out here (numbers too large?  can’t handle load?), so I’m comparing a number to its integer component via the intval() function instead.

Next Page »

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 534 other followers