Powers of 3 in binary - how can you prove this evidency?

Question

Prove that the number of 1s in the powers of 3 binary representation is (on the whole) increasing.

$3^0=1_2$ (number of 1s=1), $3^1=11_2$ (number of 1s=2), $3^2=1001_2$ (number of 1s=2), $3^3=11011_2$ (number of 1s=4), $3^4=1000101_2$ (number of 1s=3), $3^5=11110011_2$ (number of 1s=6).

So the number of 1s is increasing overall, but not at every step (3^4 has fewer 1s than 3^3). How do we prove that the number of 1s is increasing?

Answer 1

I assume that what you want to show is that the number of ones in the binary representation of $3^n$ is unbounded. Here is a sketch of how you could prove this.

First consider the binary representations of $3^{(2^n)}$, i.e. what happens when you repeatedly square $3$.

$3^1=3=11_2$
$3^2=9=1001_2$
$3^4=81=1010001_2$
$3^8=6561=1100110100001_2$
$3^{16}=43046721=10100100001101011101000001_2$
...

As you can see, the tail end of the binary representation is some number of zeroes followed by a one, and that number of zeroes increases. You can prove this very easily.

Suppose you are given any power of $3$ (not necessarily of the type given above), and the length of its binary representation is $k$ bits. From the above you can find some power of $3$ that in binary ends with at least $k-1$ zeroes followed by a one. If you multiply those two together, you get another power of $3$ that ends with the same $k$ bits as the given one, but obviously must have further ones in the rest of its binary representation.

So given any power of 3, you can find another that has more ones in its binary representation.

Answer 2

The number of binary digits of $3^n$ is approximately $n \log_2 3$. Since there's no relation between the bases $2$ and $3$ because they're coprime, we can expect that the number of $0$'s and $1$'s are about the same in each number.

So the at the long run, about half of the digits will be $0$ and half of the digits will be $1$, that is $\dfrac{\log_2(3)}{2} n$

This is of course not a rigorous proof, just a heuristic, but the experimental evidence confirms it:

Answer 3

This is a non-trivial result. A sequence is increasing if it takes every value only finitely many times. It was proved in H. G. Senge and E. G. Strauss, Period. Math. Hungar. 3 (1973), 93–100; MR0340185. They proved that the number of integers the sum of whose digits in each of the bases $a$ and $b$ lies below a fixed bound is finite, unless the bases $a$ and $b$ are multiplicatively dependent, that is, if $\log a/\log b$ is rational.

In particular $3^n$ has sum of digits $1$ in base $3$, so there can be only finitely many $n$ such that the sum of digits of $3^n$ in base $2$ is bounded by any given number: because $\log 3/\log 2$ is not rational.