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));
Can someone provide me proof of this…how it gives first k digits??
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
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).
the formula becomes
First k digits of n^n = 10^(x-floor(x)+k-1) … where x = n*log10(n)
thanks a lot for sharing this