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

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.10^m < kⁿ < (a+1).10^m

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

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 C_N be the number of appearences of {nx } in this interval for n=1,2,...,N then we have that C_N /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

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

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

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

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, log₁₀ 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

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
$\{\log a\}\ne \{\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

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

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 log_m n 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

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

Assume log₁₀ m = p/q (p, q are integers)
Therefore,
m^q = 10^p

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, m^q will be "lacking" factors and thus there exist no integer solutions for m, p and q [for HCF(m, 10) < 10]

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

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