Claudio Cherubino's blog Life of a Googler

7Apr/083

Even Digits Multiple Of Nine

The mathematical exercise we are going to solve comes from mathschallenge.net and can be summarized in a single sentence:

Find the smallest multiple of nine containing only even digits.

We just need a function to check if a number contains only even digits and then pass to it the multiples of nine.

This algorithm can be translated into the following code:

#light
open System

let isEven n = (n % 2 = 0)

let rec allEvenDigits n =
    match n with
    | n when n < 10 -> isEven n
    | n -> (isEven (n % 10)) && (allEvenDigits (Int32.div n 10))

let nums = 9 |> Seq.unfold (fun i -> Some (i, i + 9))

let answer = Seq.find allEvenDigits nums

The isEven function is just a "shortcut" for the modulus operator and it is used inside allEvenDigits, where it is applied to each digit of the given number.

Then, we have to generate the multiples of nine, but we don't know when to stop, so we need an infinite sequence, that can be produced by the Seq.unfold function.

At the end we use Seq.find, which takes a boolean function (allEvenDigits) and a sequence (nums), and returns the first element of the sequence for which the given function returns "true", i.e. the smallest multiple of nine containing only even digits, that is exactly what we had to find.

Comments (3) Trackbacks (0)
  1. I wonder how this will come out…


    head$filter (all (`elem` "02468") . show) [9,18..]

    If that’s visible at all, that’s the way I’d do it in Haskell. I don’t know the F# syntax or libs so well, but you might be able to simplify your solution along these lines. Using show to break things into digits is a bit of a hack, but show is the only use case for digitization significant enough for inclusion in the standard libs – I can’t quite convince myself it’s wrong, since digits are fundamentally defined fundamentally as a display concern.

  2. I can replace the Haskell show function with ToString().ToCharArray() to break a number into an array of digits and then I should be able to translate your code into F#.

    I don’t know if there is a better way, I’ll test a little bit more and let you know.

    Thanks for the suggestion!

  3. What about this one-liner?

    let answer = Seq.init_infinite (fun x -> Int32.to_string (9*(x+1))) |> Seq.find (String.for_all (fun digit -> (int_of_char digit) % 2 = 0))
    

    However, the initial solution is much easier to understand than these new ones.


Leave a comment

(required)

No trackbacks yet.