### The Problem

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.

### The Solution

Expressed as a ratio of "lines of text in the problem definition" to "lines of code in the solution", this is one of my longer solutions. But it works. We'll start out with some helper functions.

```
let digitize n =
let str = sprintf "%i" n
str |> Seq.map (fun x -> int(x) - int('0'))
let remove element s =
s |> Seq.filter (fun x -> x <> element)
let doubleDigits = set [11; 22; 33; 44; 55; 66; 77; 88; 99 ]
let isDoubleDigit n = Set.contains n doubleDigits
let rec gcd x y = if y = 0 then abs x else gcd y (x % y)
let fractionsEqual n1 d1 n2 d2 =
(double(n1) / double(d1)) = (double(n2) / double(d2))
let commonDigit numeratorDigits denominatorDigits =
seq { 1..9 }
|> Seq.tryFind (fun x ->
(Seq.contains x numeratorDigits) &&
(Seq.contains x denominatorDigits))
```

The `digitize`

function takes a number and turns it into a sequence of digits.

The `remove`

function takes a sequence and removes a single element from it.

The set `doubleDigits`

and the corresponding function `isDoubleDigit`

will be
used to filter out fractions that have double digits in the numerator or denominator.

The `gcd`

helper function is the classic recursive Greatest Common Denominator
algorithm. We use this to reduce the fractions we find to their "lowest common terms",
per the problem definition.

To determine if two fractions are equal, we'll use the `fractionsEqual`

function
to divide numerators by denonominators and compare the result. I was actually afraid
this wouldn't work due to the imprecision of floating point numbers, but I managed
to get the right answer using it, so I decided to not try to do a better job here.

And finally, we need a function to find the common digit between a numerator
and a denominator. The `commonDigit`

function looks for all digits, 1 through 9,
and checks to see if that digit exists in both the `numeratorDigits`

and
`denominatorDigits`

.

Now we can get to the meat of the problem: determining if a numerator and a denominator are an example of a non-trivial digit-cancelling fraction.

```
let isNonTrivialDigitCancellingFraction numerator denominator =
if numerator = denominator then false
else
let numSeq = digitize numerator
let denSeq = digitize denominator
let common = commonDigit numSeq denSeq
match common with
| None -> false
| Some d ->
let newNum = numSeq |> remove d |> Seq.exactlyOne
let newDen = denSeq |> remove d |> Seq.exactlyOne
match newDen with
| 0 -> false
| _ -> fractionsEqual numerator denominator newNum newDen
```

The function above returns false if `numerator`

and `denominator`

are equal. Otherwise,
it turns the numbers into sequences of their digits and looks for the common digit
between them. If one exists, then it removes that digit from numerator and denominator
and then returns `true`

if the new fraction is equal to the original.

And now we can solve the problem:

```
let num,den =
seq {
for num in 12..97 do
for den in (num+1)..98 -> (num,den)
}
|> Seq.filter (fun (num, den) -> not(isDoubleDigit num) && not(isDoubleDigit den))
|> Seq.filter (fun (num,den) -> isNonTrivialDigitCancellingFraction num den)
|> Seq.reduce (fun (num,den) (x,y) -> (num*x,den*y))
den / gcd num den
```

The above starts by generating possible numerators and denominators.

When generating the numerator, we can skip all the single digit numbers,
skip 10 because it has a 0 in it, and skip 11 because it's a double digit. We
generate numerators up to 97 because the largest denominator is 98 because
the denominator has to be larger than the numerator. Thus, when we generate the
denominator, we start at `num+1`

.

Next, we remove any elements where there is a double digit number in the numerator
or the denominator. You may notice we are **not** filtering out numbers that end
with 0. We could do that, but we don't really need to because `commonDigit`

only considers the digits 1-9.

Then, we filter out anything that isn't a non-trivial digit-cancelling fraction.

Then, we use `Seq.reduce`

to yield the product of all the fractions we found.

Finally, the problem definition asks for the denominator if the product fraction is expressed in lowest common terms. We find this by dividing the denominator by the Greatest Common Divisor of the numerator and denominator. This is our answer.

Other Posts in This Series