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:

<?php
$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;
		break;
	}
}


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.

Advertisements

December 14, 2014

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

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

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.

<?php
$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: , ,
Ploo!

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!

<?php
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);
					}
					break;
				}
				
				$n++;
			}
			$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.

September 19, 2014

Project Euler redux

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

A few years ago I did several of the Project Euler puzzles, a series of mathematical problems that are good programming exercises.  I started out doing them in ColdFusion, but ended up doing a a few in Python due to its better abilities at dealing with massive numbers and calculations.

I’ve now decided to convert at least some of them from CFML / Python code into PHP, as a little tutorial for myself to increase my familiarity with some of its basic syntax.  I’m doing this for basically the same reasons my colleague Adam Cameron is shifting his blog’s focus from ColdFusion to PHP.

I’m not going to try and solve the problems that I’ve already done by looking at them completely from scratch.  Instead I’ll assume my logic or approach from before was basically sound, and try to simply convert the code into PHP, perhaps with minor improvements.

What I’m  hoping is I’ll get used to common PHP functions and perhaps some gotchas that a newcomer to the language wouldn’t automatically be aware of.  If you happen to be reading any of these, have some experience in the language and spot anything daft I’m doing or know better approaches and so on, I’d appreciate any feedback.

So without further ado, here’s the first Project Euler puzzle, a load more will hopefully follow.

March 6, 2009

PHP developers most satisfied

Filed under: Web — duncan @ 12:08 am
Tags: , , , , , , ,

As reported in The Register, developers using PHP are more “satisfied” than those using other languages.

The top languages were:

  • Actionscript
  • Flex
  • Javascript
  • Microsoft F#
  • Microsoft Powershell
  • Perl
  • PHP
  • Python
  • Ruby
  • VB Script

I know what you’re thinking, “what no <insert_favourite_language_here”>? For me, that’s “what, no CFML?”

The survey was done by Evans Data. To view the press release on their website you have to register. Then to view the PDF of the report, you have to register again.

The report is 27 pages, with a page given to each of the top 10 languages, and a bit more analysis for all the major categories of the survey. They surveyed about 500 developers and IT professionals. The survey is actually for scripting languages, which is why I guess it omits several obvious popular languages. The one language in the list that is perhaps of most interest for Coldfusion developers is Flex, of which they said:

As with Actionscript, with the exception of ease of use, users gave Flex relatively low marks across the board. It did receive the second highest rating of any of these languages for quality of tools, something that most likely is attributable to the resources and support that Adobe contributes to the Flex community.

PHP, Ruby and Python all seemed to do pretty well. I’d be interested to know if they just gave developers that list of 10 pre-defined languages, or if more languages were rated, but they limited the report to the top 10 of those by usage.

Create a free website or blog at WordPress.com.