## 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.)