[Math] What are the first and last three significant digits of $n^k$.

number theory

I have two integers named $n$ and $k$. I want to find the first and last three significant digits of $n^k$.

Here $n$ and $k$ can be very large ($2 \le n < 2^{31}$ and $1 \le k \le 10^7$). What can I do in order to get the first and last $3$ significant digits of $n^k$.

I have found a way to get the most significant digits of $N^M$. The procedure is as follows :

  1. I have to use logarithms.
  2. If $X=N^M$, compute $z=3+(\log X \bmod 1)$ (base of log is $10$) and then round $y=10^z$ down to the next integer.

This should work for $X\ge 10^3$ and should give a correct answer in IEEE arithmetic for the desired range of $N$ and $M$. For smaller $X$, just compute it directly.

But what should I do in order to get the least $3$ significant digits of $n^k$?

Best Answer

The least significant 3 digits of $n^k$ are also the least significant 3 digits of

$$n^k \pmod{1000}$$

Related Question