# powers of 2 in base 3

What is the asymptotic limit of the ratio of $1s$ to $2s$ in the first digits of $2^n$ in base $3$?

If the $2^{nd},3^{rd}$ digits etc. were random but equally likely to be $0,1$ or $2$ then the ratio would be $2:1$ since if $2^n$ begins with $2$ then 2^{n+1} begins with $1$, and if $2^n$ begins with $11..10$ then $2^n+1$ begins with $2$, and if $2^n$ begins with $11...12$ then $2^{n+1}$ begins with 1.

-

Here is an elementary way to look at it: There are exactly $\lfloor n\log 3 / \log 2\rfloor = \lfloor n\log_2 3\rfloor$ powers of $2$ less than $3^n$. Of these, exactly $n$ base-$3$ representations start with a $1$, because for each $1 \le k < n$, (i) the first power of $2$ that is $k$ digits long must start with a $1$; and (ii) there can't be two successive $k$-digit powers of $2$ that start with a $1$.

So the proportion of powers of $2$ that begin with $1$ is exactly $n/\lfloor n\log_2 3\rfloor$, which tends to $1/\log_2 3 = \log_3 2$.

Updated to add: This method doesn't generalise very well, except to show the following:

Given positive integers $a,b$ with $a < b$, then the proportion of powers of $a$ whose first base-$b$ digit is less than $a$ is $\log_b a$.

-
Very nice (although I suspect the going will get harder if you try to compute the proportion starting with, say, 102 by this method). –  Gerry Myerson Apr 3 '12 at 10:11
@Gerry: Yes! See my update. –  TonyK Apr 3 '12 at 15:08

$\log2$ is irrational, so $n\log2$ is uniformly distributed modulo 1, but $n\log2=\log2^n$. This means you get a Benford's Law distribution (which see - surely there is a lot about this on the web). In particular, the proportion of times the first digit is a 1 is $\log_32$, but you can work out the proportion of times any given finite string appears as the first (base 3) digits.

-
Could you clarify why irrationality of log2 implies uniform distribution for n*log2? –  rank Apr 3 '12 at 10:51
@rank: It's not trivial! See this MO question or this Wikipedia page (though neither give a proof). –  TonyK Apr 3 '12 at 11:16
@TonyK Thank you, I found a proof with the keywords. –  rank Apr 4 '12 at 5:34