# First k digits of n^n

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

7 Likes

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.

34 Likes

Thank you so much. thanks a lot for sharing this 