Tuesday, 14 July 2015

Problem of Nines

Here is a pretty problem from Programming Praxis that has popped up on Planet Scheme... what is the lowest number that is a multiple of 23 that is made of only the digits 0 and 9?

One way to find it would be to scan through all the numbers made of 0s and 9s.  This looks tricky until you see the numbers:


Aha, you say, these are just like binary numbers:


Except take each one and multiply by 9 and Bob's your uncle you have all the numbers made of 0s and 9s.  Scan through and pick the first one that is a multiple of 23.  I'll try that approach later when I've figured out how you convert a number to a binary digit sequence.  Must be a simple way.

However the alternative path to the solution is to produce the list of multiples of 23 and pick the first one that is made only of 0s and 9s.

Now the multiples of 23 are easy - it's just [23,46..]:

Prelude> take 10 [23,46..]

And the condition that the number is made of 0s and 9s? - well, given a number n we say read n to convert to a string, which is just a list of characters: we can then use the function all to apply the test to this list that all the characters are either 9 or 0, that is to say all are an element of the list "90"  - we use the function elem for this:

Prelude> all (`elem` "09") "9080"
Prelude> all (`elem` "09") "9090"

So we set up a list of all numbers n drawn from the multiples [23,46..] subject to the condition that all the characters of the string representation of n are in the list "90" - in other words

[ n | n <- [23,46..], all (`elem` "90") (show n) ]

Of course this is an infinite list, but we just ask for the first element, i.e. the head, as follows:

Prelude> head [ n | n <- [23,46..], all (`elem` "90") (show n) ]

So the answer is 990909.  In fact let's see the first 10 solutions:

Prelude> take 10 [ n | n <- [23,46..], all (\c -> c=='0' || c=='9') (show n) ]

An infinite list is like the Tao, it seems empty, but draw upon it and it is never exhausted - - although in this case I gave up waiting after the eighth answer...

No comments:

Post a Comment