Internet Problem Solving Contest

IPSC 2005

Solution to Problem I – Ignore the Garbage

The digits that can be read upside-down are 0,1,2,5,6,8 and 9. A number can be turned upside down iff it doesn't contain any other digits. Let's write down first few numbers containing only these digits: 1, 2, 5, 6, 8, 9, 10, 11, 12, 15, 16, 18, 19, 20, 21, 22, 25, ....

Now note that if we used the digits 0-6 instead of our 7 digits, the sequence would contain all base-7 numbers in the correct order.

Given a number K, how do we get the K-th number we see on the display? The easiest way starts by converting K to base 7. Now we can simply "relabel" its digits to get the K-th "turnable" number, reverse the string and finally replace each 6 by 9 and vice versa. (The other digits don't change when turned upside down.)