number theory - Prove that $r(2^{55555})$ divisible by $5^5$

In this question there is a comment by @amclade, that

$$r\left(2^{55555}\right) \equiv 0 \pmod{5^5},$$

where $r : \mathbb{N} \rightarrow \mathbb{N}$ function gives the reverse of a number.

I've checked this using Maple, and the statements seems to be true – verified by a CAS –, but how could we prove it analytically?

Answer

It is easy to check that $5^5=3125$. Note that because $100000 \equiv 0 \mod 3125$, the divisibility of a decimal number by $3125$ can be checked simply by inspecting the last $5$ digits.

So it remains to compute the first $5$ digits of $2^{55555}$. First let's compute the number of digits of this number. This can be done with the computation $\lceil 55555 \log_{10} 2 \rceil= 16724$.

This means the relevant digits can be multiplied by $10^{16719}$ to approximate the number from below. So our computation becomes $\frac{2^{55555}}{10^{16719}}$, which will spit out the first $5$ digits of the number (decimal places can be discarded). Doing a trivial simplification leaves $\frac{2^{38836}}{5^{16719}}$.

Computation is inevitable, but only the first $5$ significant figures are needed. It is convenient to take the logarithm of this fraction.

$${\log \frac{2^{38836}}{5^{16719}}}={38836 \log 2 - 16719 \log{5}}$$

For good measure, we'll compute this to $10$ significant figures. The result is $10.8714462403$. Now taking $e^{10.8714462403}$, we have $52651$. Reversing this much smaller number, we identify it as a multiple of $3125$ and complete the proof.

---

The number of computations needed with this approach is much lower than the naive method of exponentiation. A more intelligent means of taking $2^{55555}$ to $5$ decimal places of precision (which is what the above accomplishes) may be more efficient for a computer to do:

$$2^{55555} = 2^{32768} 2^{16384} 2^{4096} 2^{2048} 2^{256} 2^2$$

The computer simply computes $2$ to sufficient precision, and squares the number each time. These operations are very fast and the result will be computed very quickly, likely faster than computing logarithms.