What’s the 100-th digit of $2^{10000}$?

Question

I found this question on a Chinese programmer forum. They solved it by brute-force method like 2 ** 10000[99] in python. The solution is 9. I’m wondering if we can solve it in a better way? Do we have to calculate $2^{10000}$ first?

I don’t even know what tags I should put. Any suggestions or modifications would be appreciated.

Answer 1

There is no need to compute $2^{10000}$ in full. You can perform all multiplies keeping only the $m$ most significant digits. If you implement truncated multiplication, you obtain the result after $13$ squarings and $4$ multiplies.

$m$ must be a little larger than $100$ to shield against truncation errors. Unfortunately, I am unable to compute the minimum $m$ required.

Taking $m=110$, I obtained the number

$$\begin{align}&1995063116\ 8807583848\ 8374216268\ 3585083823\ 4968318861\\&9245485200\ 8949852943\ 8830221946\ 6319199616\ 840361945\color{red}9\\&7899331113\end{align}$$

Answer 2

In my opinion the only optimization would be to calcultate $2^{10000}$ in a smarter way:

$$2^{10000}=2^{8192}\times2^{1024}\times2^{512}\times2^{256}\times2^{16}$$

In python:

p16=2**16
p256=p16**16
p512=p256**2
p1024=p512**2
p8192=p1024**8
res=p8192*p1024*p512*p256*p16
print(str(res)[99])

Bigger exponents are evaluaed by using already calculated values of the smaller exponents.

The code prints 9.