There is no $n$ such that the digits of $16^n$ form a decreasing sequence.

Question

Show that there is no $n$ such that the digits of $16^n$ in base $10$ form a (non necessarily strictly) decreasing sequence. For example $64$ or $9331$ are decreasing sequences.

You can bash this mod $10^k$ for some big (but fixed) $k$ but as this was an exam problem I would like to see a more computation free approach.

Answer 1

Observation 1: The last digit of $16^n$ is always 6.

Observation 2: The last 2 digits of $16^n$ is divisible by 4, so have to be 76 or 96 in order for the string to be decreasing.

Observation 3: $n \geq 7$ by checking the first few cases. (In fact, we just need to check $n = 3, 5 $ due to observation 2.)

Observation 4: $16^n > 10^n$, so we can talk about the last $n$ digits without worrying about an initial string of 0's. (This is helpful with the subtraction later.) This last $n$ digits must be a multiple of $2^n$.

Observation 5: If $16^n \equiv 96 \pmod{100}$, then for a decreasing string we must have $ 16^n \equiv 10^n - 4 \pmod{10^n}$, which is not a multiple of $8$. So $ n\leq 2$, which we have ruled out.

We now focus on $16^n \equiv 76 \pmod{100}$. For a decreasing string, it looks like $\underbrace{9\ldots9}_{x} \underbrace{8\ldots8}_{y} \underbrace{7\ldots7}_{z} 6$.
Then $ 16^n \equiv 10^n - \underbrace{1\ldots1}_{a} \underbrace{2\ldots2}_{b}4 \pmod{10^n}$.
Set $R = \underbrace{1\ldots1}_{a} \underbrace{2\ldots2}_{b}4$, which is a multiple of $2^n$. (Note that $ a + b \leq n-1$, though we will not use it.)

Observation 6: For $\underbrace{1\ldots1}_{a} \underbrace{2\ldots2}_{b}4$ to be a multiple of 4, it must be $\underbrace{1\ldots1}_{a} \underbrace{2\ldots2}_{b-1}24$.

Observation 7: For $\underbrace{1\ldots1}_{a} \underbrace{2\ldots2}_{b-1}24$ to be a multiple of 8, since 24 is divisible by 8, the prior digit must be 2, so it must be $\underbrace{1\ldots1}_{a} \underbrace{2\ldots2}_{b-2}224$.

Observation 8: For $\underbrace{1\ldots1}_{a} \underbrace{2\ldots2}_{b-1}24$ to be a multiple of 16, since 224 is divisible by 16, the prior digit must be 2, so it must be $\underbrace{1\ldots1}_{a-1}\underbrace{2\ldots2}_{b-3}2224$.

Observation 9: For $\underbrace{1\ldots1}_{a-1}\underbrace{2\ldots2}_{b-3}2224$ to be a multiple of 32, since 2224 is NOT divisible by 32, the prior digit must be 1, so it must be $\underbrace{1\ldots1}_{a-1}12224$.

Observation 10: $112224$ is not a multiple of 64. So $n \leq 6$.

---

Notes

• As you'd have realized, the leading string of 1, 2 is initially not restrictive. If we had a choice of even and odd, then we can always continue the string.
• However, once we're forced to choose 1 (odd), then our only remaining choices are 1 (odd), and it cannot always be continued. That's the motivation for Observation 6-10.