Number of digits in 125^100
Source: Asked to me by Suman Kalyan Bera (M.Tech Student IIT Delhi) on contact page
Problem:
How many digits does the number 125^100 have?
Very interesting problem and equally interesting solution :)
Update (25 December 2011):
You are not allowed to use your high school notes on values of log_10(2) or log_10(5)
Solution:
Posted by me in comments!
Problem:
How many digits does the number 125^100 have?
Very interesting problem and equally interesting solution :)
Update (25 December 2011):
You are not allowed to use your high school notes on values of log_10(2) or log_10(5)
Solution:
Posted by me in comments!
solution :P
ReplyDelete#include< cstdio >
#include< sstream >
#include< cstdlib >
#include< cctype >
#include< cmath >
#include< algorithm >
#include< set >
#include< queue >
#include< stack >
#include< list >
#include< iostream >
#include< fstream >
#include< numeric >
#include< string >
#include< vector >
#include< cstring >
#include< map >
#include< iterator >
#include< bitset >
using namespace std;
#define sf scanf
#define pf printf
#define re return
#define i64 __int64
#define I64 %I64d
#define u64 unsigned __int64
#define U64 "%U64d"
#define ll long long
#define forit(i, m) for (i=(m).begin(); i!=(m).end(); ++i)
#define rab(i,a,b) for(i=a;i<=b;i++)
#define ras(i,a,b) for(i=a;i>=b;i--)
#define rep(i,n) rab(i,0,n-1)
#define fi(n) rep(i,n)
#define fj(n) rep(j,n)
#define fk(n) rep(k,n)
#define max(a,b) a>b? a:b
#define min(a,b) aeps)
#define inf (1<<30)
#define pi 2*acos(0.0)
#define Set(t,v) memset((t), (v), sizeof(t))
#define pb push_back
#define sz(v) (v).size()
#define vt vector
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rev(x) reverse(all(x))
#define im int main()
#define sq(a) (a)*(a)
#define max 1000001
ll gcd(ll a,ll b){while(b){b ^=a ^=b ^=a %=b;}return a;}
im
{
char a[max];
sf("%s",&a);
pf("%d\n",strlen(a));
re 0;
}
The number of digits in a number x equal log of x (to the base 10)
ReplyDeleteIn this case 100*log(125)
log_10(125^100) = 209.691001
ReplyDeleteHence 209 digits
taking log(base 10) of 125^100 it gives the number of digit it contains
ReplyDelete125^100 = 5^300. We know log5 is 1-log2 = 0.6990 (from my JEE prep days). 300*.699 = 209.7. Therefore 210 digits. Yeh bhee koi question hai?!? Or am I missing something?
ReplyDeleteThe number of digits is floor(log_10 125^100) + 1 = floor (log_10 5^300) + 1 = floor(300(1-log_10 2)) + 1 which is to enough digits of accuracy, floor (300 - 300*0.3010) + 1 = 210.
ReplyDeleteBut, certainly the fact that I knew log_10 2 is roughly 0.3010 came in handy here.
300, I'd say.
ReplyDeleteK=125^100.
ReplyDeleteNo.of Digits=floor(log K)+1
log(K)= 300-100*log8=300-300*log2=209.3
Ans=210.
isn't is just solving for n where n satisfies:
ReplyDelete10^(n+1)>= 125^100 >= 10^n
n solves to 209
thus 210 digits long (google calculator says its right)
Ok. May be I should have been clear. Most people do not know what log_10(2) or log_10(5) is!
ReplyDeleteYou have to find the answer without using your high school notes, by pure logic.
Solution:
125^100 = 1000^100/(2^300)
2^300 = 1024^30
125^100 = 1000^70/(1.024^30)
Claim: 1 < 1.024^30 < 10
So, 10^209 < 125^100 < 10^210
Number of digits = 210 :)
Regarding my claim about 1.024^30 < 10
ReplyDelete(1+x)^30 = 1 + 30x + 30C2*x*x + 30C3*x*x*x + ...
Each subsequent term is a factor of less than 30C(i+1)*x/30C(i) of the previous term, i.e.
x*(30-i)/(i+1) < 30x for all i
30x = y = 0.72
(1+x)^30 < 1 + y + y*y + ... 31 terms
(1+x)^30 < 1/(1-y) < 10
Hence, done
@khalil, nick, mani, sid, circem, avinash, siva
I guess all of you did the same thing, with some mistakes at some places, but the argument was pretty much the same. Thanks
@Anik,
how is this the solution?
another way of proving the claim which doesn't require knowledge of binomial theorem :-
ReplyDelete(1.024)^30 < 10
it is sufficient if we prove (1.024)^32 < 10
it would be sufficient if we prove
(1.024)^16 <3
it wud be sufficient if we prove
(1.024)^8<1.7
it wud be sufficient if we prove
(1.024)^4 < 1.3
it wud be sufficient if we prove
(1.05)^2 < 1.3 (by squaring 1.024)
1.1025< 1.3 which is true.