0

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?

xxxx036
  • 773
Alexandru Ghiveciu
  • 13

3 Answers3

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.

markvs
  • 19,653
  • What do you mean by ;integers the sum of whose digits in each of the bases a and b lies below a fixed bound;? For an integer, do you add the digits in each of the two bases, and then add the two results, and this sum of sums is unbound (with finite exceptions)? – Alexandru Ghiveciu Feb 25 '22 at 16:30
  • @AlexandruGhiveciu Fix a number $N$ then the set of natural numbers whose sums of digits in base $a$ and base $b$ are $<N$ is finite. – markvs Feb 25 '22 at 18:47
1

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:

enter image description here

jjagmath
  • 18,214
0

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.

Jaap Scherphuis
  • 13,660
  • "Unbounded" is much weaker than "increasing". The latter means that the sequence takes each value finitely many times. – markvs Feb 25 '22 at 15:45
  • It is not obvious. Maybe the first term is something like 1110011100000001(7 zeros tail) and the second something like 1110110000001(6 zeroes tail), the rezult can be something like 1100001000000010000001 (with less 1s overall). It has a tail with one more 1, but we cant assume anything about the front of the number. – Alexandru Ghiveciu Feb 25 '22 at 16:08
  • @AlexandruGhiveciu For example, $3^3=27=11011_2$ has 4 ones. It has length 5. Multiply this by $3^8$ which has a tail of length 5 of the form $00001_2$. This results in a larger power of 3 that has a tail of length 5 of the form $11011_2$ and therefore has more than 4 ones. – Jaap Scherphuis Feb 25 '22 at 16:20
  • @JaapScherphuis Wow, now I get it. This solves it. And for 3^(2n), every +1 in n gives another 0 in the tail. Brilliant. Thank you! – Alexandru Ghiveciu Feb 25 '22 at 16:57
  • @AlexandruGhiveciu Note however that markvs is right that what I prove here is much weaker than what most people apparently think of as increasing. I show that there is no upper bound to the number of ones, but this says nothing about whether numbers with few ones get rarer or whether there is some kind of average trend to it. – Jaap Scherphuis Feb 25 '22 at 17:07
  • Euclid didn,t say if primes get rarer or not, but he proved they were infinite. What you proved counts as increasing in my book. The only other meaning of increasing would be 1s increasing for every extra power of 3, witch is not the case. As for the trend, aparently the number of 1s steadily increase (but proving this is beyond me, and I am not interested in this) – Alexandru Ghiveciu Feb 25 '22 at 17:25