Leftmost Digits of 2^n

Date: 11/01/2002 at 16:06:41
From: Claudio Buffara
Subject: Leftmost digits of 2^n

Hi,

Here is my problem: Prove that there is a power of 2 whose decimal 
representation starts with the digits 1999.

A hint was given: log of 10 in the base 2 is irrational.

The way I see it, I must prove there exist positive integers m, n, 
and A such that: 2^m = 1999 * 10^n + A, where 1 <= A <= 10^n - 1.

I can't see any obvious way to use the hint.

I did some algebraic manipulations, such as:

   A = 2^m - 1999*10^n = 2^n*(2^(m-n) - 1999*5^n)

and deduced that: 

   2^n || A ==> A = 2^n * b, where b is odd.

Also, 

   1 <= A <= 10^n - 1  ==>  1 <= b <= 5^n - 1.

And that was as far as I got.

I'd really appreciate some help from you.

Thanks and regards,
Claudio Buffara.

Date: 11/01/2002 at 17:03:59
From: Doctor Schwa
Subject: Re: Leftmost digits of 2^n

Hi Claudio,

To use the hint, let's rewrite your statement about 2^m and A instead 
as proving that there's some m and n so that

   1999 * 10^n < 2^m < 2000 * 10^n

Taking log base 10 of both sides,

   log(1999) + n < m log 2 < log(2000) + n

and you know log 2 is irrational. Can you use that to prove that some 
multiple of log 2 is between log(1999) and log(2000), mod 1? (mod 1 
means taking the fractional part; the n can take care of the integer 
part.)

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/04/2002 at 08:45:09
From: Claudio Buffara
Subject: Leftmost digits of 2^n

Got it!

Your inequalities: n + log(1999) < m*log(2) < n + log(2000) can be 
rewritten as: log(1999) < -n + m*log(2) < log(2000).

However, given that log(2) is irrational, it is true that for any 
epsilon > 0, there are positive integers a and b such that:
0 < | -a + b*log(2) | < epsilon  -  a result that can be proved by 
means of the pigeonhole principle (in fact, I never saw a proof of 
that which doesn't use the PHP - I'd be very interested to see if one 
exists).

That, in turn, implies that the numbers of the form '-p + q*log(2)' 
with p &amp; q positive integers are dense in R (given any interval 
(u,v), set epsilon = (v-u)/2 in the above inequality and take a and b 
such that 0 < | -a + b*log(2) | < (v-u)/2. Then, by the Archimedean 
property of R, some integer multiple of -a + b*log(2) must fall 
inside (u,v) ).

In particular, there are positive integers m and n such that:

   log(1999) < -n + m*log(2) < log(2000)  ==>

   1999 < 10^(-n) * 2^m < 2000  ==>  

   1999 * 10^n < 2^m < 2000 * 10^n  ==>

the first four digits of 2^n are 1999.....

Thanks a lot for your help.

Best regards,
Claudio Buffara.

Date: 11/04/2002 at 09:55:06
From: Claudio Buffara
Subject: Leftmost digits of 2^n

I think the problem has a sweeping generalization:

Let P be a positive integer that is not a power of 10 (so that log(P) 
is irrational) and let A1,A2,...,Ar be any sequence of decimal digits. 
Then there is a power of P whose decimal representation starts with 
the digits A1...Ar.

Let A = A1*10^(r-1) + A2*10^(r-2) + ... + Ar.

We must show that it is always possible to find positive integers m 
and n such that: A*10^n < P^m < (A+1)*10^n.

But due to the irrationality of log(P), the proof is identical to the 
one for the power of 2.

Best regards,
Claudio Buffara.

Date: 11/04/2002 at 13:18:07
From: Doctor Schwa
Subject: Re: Leftmost digits of 2^n

Exactly so. You can make the leftmost digits be any string you want,
as long as log(P) is irrational.

It's quite a different story if you want to study the rightmost 
digits. That's a number theory problem, and quite a fun one.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/