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