Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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? –  User58220 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. –  User58220 Feb 13 '13 at 6:16
add comment

2 Answers

up vote 0 down vote accepted

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

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

share|improve this answer
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.