# What are the first and last three significant digits of $n^k$.

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$?

-
Which digits of n contribute the the three least significant digits of $n^k$? How many different 3-digit numbers can you get by successive multiplications, before they begin to repeat? – DJohnM Feb 13 '13 at 4:42
Successive Multiplications ?? i couldn't get your question . – Way to infinity Feb 13 '13 at 4:47
Suppose the number is .....189, and it's raised to the 478,219th power. As you multiply over and over again, the last three digits cycle through 721, 269, 841, 949, and so on. There's at most 1000 possible values. Once you hit one already used, you're in a loop and the the cycle repeats. – DJohnM Feb 13 '13 at 6:16

The least significant 3 digits of $n^k$ are also the least significant 3 digits of
$$n^k \pmod{1000}$$
The least significant 3 digits of $n^k$ are also the least significant 3 digits of $(n \bmod 1000)^k$, i.e., you need to compute $(n \bmod 1000)^k$ modulo 1000. By using exponentiation by squaring you can compute the result without too much trouble ($1000 \cdot 1000$ fits comfortably into 32 bits, typically an int in e.g. C).