*Posted by Mitchell in : potd , trackback
*
Let $a_n$, for $n$ a positive integer, be the $n$th smallest positive integer whose decimal (base-$10$) representation contains no occurrence of the same digit twice in a row. Find $ a_{ 82^6}$.

show

**Solution:**
There are (by a simple constructive counting argument) $9^k$ $a_i$ which have exactly $k$ digits. This means that $9 + 9^2 + \cdots + 9^{11}$ of the $a_i$ have $11$ digits or fewer, and $9 + 9^2 + \cdots + 9^{12}$ have $12$ digits or fewer, which means that $a_{82^6}$ (since $82^6$ is between these two numbers) has $12$ digits. Additionally, it is the $N = 82^6 – 1 – 9 – \cdots – 9^{11}$th smallest $12$-digit positive integer (zero-indexed) with no occurrence of the same digit twice in a row.

To find the twelve digits, we perform the following steps: write $N$ in base $9$, left-padding with zeros until the number is $12$ digits long, to get $(d_1 d_2 \cdots d_{12})_9$ (where the subscript means base $9$). Then, let $e_1 = d_1 + 1$, and for $2 \leq i \leq 12$, $e_i = d_i$ if $d_i < e_{i – 1}$, and $e_i = d_i + 1$ otherwise.

Then, the desired digits will be $(e_1 e_2 \cdots e_{12})_{10}$.

To prove that this works, it is sufficient to note that this mapping forms an increasing bijection between sequences $(d_1 d_2 \cdots d_{12})_9$ of $12$ digits from $0$ to $8$ and sequences $(e_1 e_2 \cdots e_{12})_{10}$ of $12$ digits from $0$ to $9$, starting with a nonzero digit and with the property that no digit is repeated twice in a row. This is not difficult to prove.

So we first write $N = 82^6 – 1 – 9 – \cdots – 9^{11}$ in base $9$. To do this, we use the binomial theorem: \[\begin{align*}82^6 &= (9^2 + 1)^6 \\&= 9^{12} + 6 \cdot 9^{10} + 15 \cdot 9^8 + 20 \cdot 9^6 + 15 \cdot 9^4 + 6 \cdot 9^2 + 1 \\&= (1061622160601)_9\end{align*}\] $1 + 9 + \cdots + 9^{11}$ written in base $9$ is simply $(111111111111)_9$, so subtracting (in base 9), we get that $N$ is $(850511048480)_9$. Applying the algorithm, we arrive at the final answer of \[\boxed{950612059490}.\]

## Comments»

no comments yet - be the first?