First k digits of n^n

general
,
1

It is related to problem :http://www.codechef.com/problems/MARCHA4
where we are supposed to find first and last k digits of n^n.
To find first k digits i have seen people using some log and floor functions…complete code is below:

long int firstKdigits(long long n,int k)

{
long double x, y;

x = n*log10(n);

y = floor(pow(10,x-floor(x) +k-1));

return ((int)y);

}

Can someone provide me proof of this…how it gives first k digits??

6 Likes
2

Ok lets solve by taking an example

Eg:- n = 2013 and k = 4.

Now we have to find the first 4 digits of 2013^2013

Let,

x = 2013^2013

Taking log(base 10) both sides we get,

log(x) = log(2013^2013)

Bringing the power down ,

log(x) = 2013 * log(2013)

Putting the values we get,

log(x) = 6650.63751
log(x) = 6650 + 0.63751

Now raising both sides with base 10,

x = (10^6650) * (10^0.63751)
x = (10^6650) * y

Now (10^6650) will not affect the digits since it only shifts the decimal place.

Now y = (10^0.63751) = 4.34020 (approx.)

So now to get the first 4 digits multiply y by 10^3,

Thus, first 4 digits of 2013^2013 are 4340.

From this the formula becomes ,

First k digits of n^n = 10^(y) * 10^(k-1)

Now y = fractional part of x = x - floor(x) where x = n*log10(n).

Thus,

the formula becomes

First k digits of n^n = 10^(x-floor(x)+k-1) … where x = n*log10(n)

Hence Solved.

30 Likes
3

Thank you so much.:slight_smile:

4

thanks a lot for sharing this :slight_smile: