Duncan's blog

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:

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: