[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1906.0. "Powers of 2 digits" by EVTSG8::ESANU (Au temps pour moi) Mon Nov 14 1994 07:18

For any finite sequence of base 10 digits there exists a
power of 2 whose writing in base 10 begins precisely with
those digits.

Generalizations?

Does anyone know who the author of this problem is?

Mihai.
T.RTitleUserPersonal
Name
DateLines
1906.1HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Mon Nov 14 1994 18:101
What about "111".  I don't think any power of 2 start with "111".
1906.2CSC32::D_DERAMODan D'Eramo, Customer Support CenterMon Nov 14 1994 19:483
        2^143 = 11150372599265311570767859136324180752990208
        
        Dan
1906.3My stab at it...SSAG::LARYLaughter & hope & a sock in the eyeMon Nov 14 1994 20:3752
>For any finite sequence of base 10 digits there exists a
>power of 2 whose writing in base 10 begins precisely with
>those digits.
>
>Generalizations?

It would seem that this would be true for any integer base b > 1 and any x > 1
such that log[base b](x) is irrational, based on a fairly easy to prove theorem
that says if a is irrational there are infinitely many (p,q) such that 
abs(a - p/q) < 1/q^2. 

Since there are infinitely many such (p,q), there must be some with q larger
than any given finite bound. Pick such a (p,q) with q > ln(b)*(b^(n+1) + 1),
where n >=1 is the number of digits you want to match. 

By the theorem, -1/q^2 < log[base b](x) - p/q < 1/q^2.

Multiply by q,

	-1/q < q*log[base b](x) - p < 1/q

Since b^x is monotonic increasing we can exponentiate base b,

	b^(-1/q) < (x^q)/(b^p) < b^(1/q)

For all y, b^(y/ln(b)) = (b^(1/ln(b)))^y = (b^(log[base b](e)))^y = e^y, so
this is equivalent to 

	e^(-1/(b^(n+1)+1)) < (x^q)/(b^p) < e^(1/(b^(n+1)+1))

For all y > 1, e^(1/y) < 1/(1-1/y) = 1 + 1/(y-1) by comparing series
expansions, so

	e^(1/(b^(n+1)+1)) < 1 + 1/b^(n+1) and similiarly
	e^(-1/(b^(n+1)+1)) > 1 - 1/b^(n+1)

i.e. (x^q)/(b^p) is within b^-(n+1) of 1.

So for any number z, the first n digits base b of z * (x^q)/(b^p) should either
be the same as the first n digits of z, or different by one (wrapping around
from the largest n-digit number to 10000... and vice versa), and the difference
will always be in the same direction (positive or negative).

Therefore, the powers of (x^q)/(b^p) should cover all possible combinations of
first n significant digits base b, and therefore so should the powers of x^q,
since all the b^p factor does is fiddle with the "decimal point".

You could generalize this to x < 1 as well if you didn't include leading zeros
(and minus signs) as digits.

Note that this means when b = 10 the leading n digits of the powers of any
integer that isn't itself a power of 10 will assume all possible values.
1906.4re. .3: Another proof of .0EVTSG8::ESANUAu temps pour moiWed Nov 16 1994 12:5347
Nice stab, Richie! I didn't know this proof - here is mine:


Proposition. Let  a,b > 0 . Then the set

	{m*a - n*b / m,n in N}

is dense in  R  if and only if  a/b  is irrational.


Corollary. Let  a,b > 0 . Then the set

	{(a^m) / (b^n) / m,n in N}

is dense in  (0,oo)  if and only if  log[base b](a)  is irrational.


(I have my own proof for the classical proposition above).


Generalization of .0:

Let  p,q  be natural numbers,  p,q >= 2 , such that  log[base q](p)  is
irrational and consider a finite sequence of base p  digits. Then there is
a power of  q  whose writing in base  p  begins precisely with those
digits.

Proof:

Let  c(1),...,c(s)  be the finite sequence of base p  digits and let A  be
the number whose base  p  writing digits are precisely  c(1),...,c(s) .

The corollary above tells us that the set {(q^n) / (p^m) / m,n in N}  is
dense in  (0,oo) . Hence there are natural  m,n  such that

	A * p^s  <=  (q^n) / (p^m)  <=  A * p^s + 1 - 1/(p^m)
Then
	0  <=  q^n - A * p^(m + s)  <=  p^m - 1

Let  x = q^n - A * p^(m + s) , that is  q^n = A * p^(m + s) + x . We also
have  x < p^m ,  hence  x  is written in base p  using  m  base p  digits
x(1),...,x(m)  (add zeros at the beginning if necessary).

As  A  is written  c(1),...c(s)  in base p ,  q^n  is written in base p 
using the digits  c(1),...,c(s),x(1),...,x(m) , q.e.d.

Mihai.