# Duncan's blog

## 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

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.