Welcome to NRICH.

 
Powers of 3 giving any sequence of digits
By Yatir Halevi on Wednesday, October 16, 2002 - 07:51 pm:

I have just seen a most remarkable theorem:
For every sequence of digits there is a power of 3 that starts with that sequence.

Can anybody prove it?

Yatir

By Andre Rzym on Wednesday, October 16, 2002 - 09:29 pm:

I would approach it as follows: for a given integer, k, and a given sequence, a, then we need to find m and n (integers) such that

a.10m < kn <(a+1).10m

Taking logs

ln(a) < n.ln(k) - m.ln(10) < ln(a+1)

I think you run into trouble finding m,n if ln(k) is a multiple of ln(10)!

Andre

By Demetres Christofides on Thursday, October 17, 2002 - 09:40 am:

Actually, I would prefer taking logarithms to the base 10. Then you need to find integers m and n such that

log(a) < nlog(k) - m < log(a+1)

To prove the result you need a theorem (I think called the equidistribution theorem) which says that if x is irrational then the sequence {nx} is equidistributed in (0,1). This means that for any subinterval (a,b) of (0,1), if we let CN be the number of appearences of {nx} in this interval for n=1,2,...,N then we have that CN/N tends to b-a as N tends to infinity.

This will complete the proof as long as log(k) is irrational. Can you see why ?
I think log(k) should be irrational as long as k is not a power of 10 but I am not absolutely certain.

Ok I've just looked it up in mathworld
and log(k) is irrational for k not a power of 10.

Can you complete the proof now ?

Demetres

By Yatir Halevi on Thursday, October 17, 2002 - 10:00 am:

I think so.
({log(a)},{log(a+1)}) is a subinterval of (0,1) that means that for every z we can find an n such that {nz} is in our subinterval (because of the equidistribution theorem).
If log(k) is an irrational number then obviously we can choose an n and m such that they lie in the interval (log(a),log(a+1)) because all we have to do is choose an n such that nlog(k)>log(a+1) and choose an m in such way to make nlog(k)-m be in that interval.

An interesting question would be how many different powers of 3 do we have that start with a certain string a.


Yatir

By Demetres Christofides on Thursday, October 17, 2002 - 01:37 pm:

Not exactly. You should say that you choose an n such that nlog(k) > log(a+1) AND {nlogk} lies in the interval. Then it is obvious that you can choose the m such that nlogk-m lies in the interval. I believe that is what you meant.
[Actually you need a bit more care in the case that {log(a+1)} is less than {log(a)}]

If you have a closer look at the equidistibution theorem you will see why there are infinitely many powers of 3 that start with the same string a. If not then ask me to explain.

Demetres

By Demetres Christofides on Thursday, October 17, 2002 - 01:39 pm:

Something more. Why is {log(a)} never equal to {log(a+1)} ? You should also explain this because otherwise you cannot apply the equidistribution theorem.

Demetres

By David Loeffler on Thursday, October 17, 2002 - 01:55 pm:

Observation: The equidistribution theorem is a bit strong for this problem; it is sufficient to use a slightly weaker theorem called Kronecker's theorem which states that {nz} is dense in (0,1). This is vastly easier to prove (Hardy + Wright's Introduction to the Theory of Numbers presents about a dozen different proofs, at least one of which can be fiddled to give us an upper bound on how large n will have to be.)

Fun exercise: prove that if k is not a power of 10, log10 k is irrational. (Harder exercise: prove that it's transcendental.)

Feel free to ignore this comment, I just thought somebody might find it interesting.

David

By Yatir Halevi on Thursday, October 17, 2002 - 04:11 pm:

if {loga}={log(a+1)} then
loga=n+R
log(a+1)=m+R
(where n and m are integers and R is the irrational fractional part)
m>n because otherwise 0=1
log((a+1)/a)=m-n
because gcd(a+1,a)=1, this obviously wrong!
and thus
{loga}¹{log(a+1)}

David, what do you mean by dense? how is it different from the equidistribution?
I will try your exercise, sounds fun!


Yatir

By Yatir Halevi on Thursday, October 17, 2002 - 04:30 pm:

David,
I didn't prove it to be irrational, but if it is then it MUST be transcendental by Gelfond's Theorem (which I know is cheating!)


Yatir

By Demetres Christofides on Thursday, October 17, 2002 - 04:31 pm:

Yatir, suppose we have two subsets A,B of the such that AÍB. Then we say that A is dense in B if for any point x of B and any e > 0 (however small it is) there is a y in A such that |x-y| < e. What do we mean by that ? We mean that for any x in B there are points in A as close as we like to x. Tell me if you want me to explain more about this. The difference between the terms equidistribution and dense is very nicely explained in http://mathworld.wolfram.com/EquidistributedSequence.html.

Finally a hint about the irrationality of logmn for m,n natural numbers where n is not a power of m: The result depends only on the existence and uniqueness of prime factorisation.

Demetres

By Marcos Charalambides on Thursday, October 17, 2002 - 06:31 pm:

For the irrationality of log10 m can you use this idea or am i assuming anything I'm not supposed to:

Assume log10 m = p/q (p, q are integers)
Therefore,
mq = 10p

Now, m, p and q are integers where HCF(m, 10) < 10
m will be divisible by 5 OR by 2 OR by neither. In each case, using the fact that you can write a number as a product of primes in only one way, mq will be "lacking" factors and thus there exist no integer solutions for m, p and q [for HCF(m, 10) < 10]

By Demetres Christofides on Thursday, October 17, 2002 - 07:11 pm:

That's exactly the idea Marco, but can you write it down in a better way ? (i.e. don't use phrases like 'lacking factors'.) The same idea works not only if the logarithmic base is 10, but also if it is any other integer. Can you also prove that ?

Demetres

By Vicky Neale on Friday, October 18, 2002 - 09:17 am:


I discovered a rather interesting page about algebraic numbers yesterday; it requires a bit of basic knowledge about linear algebra, but that is all. http://www.dpmms.cam.ac.uk/~wtg10/galois.html

It contains a (in my opinion rather neat) way of showing that certain numbers are algebraic, and also discusses what you get if you consider the roots of polynomials with algebraic coefficients.

Vicky