Representation of powers of three in binary.

Question

Do powers of $3$ have a simple representation in binary ? I fail to spot an obvious pattern or anything else. The only thing I can think of is using the binomial theorem $$3^n = (1+2)^n = \sum_{k=0}^n {{n}\choose{k}}2^k 1^{n-k} = \sum_{k=0}^n {{n}\choose{k}}2^k $$ However this doesn't really help.

Answer 1

This question is related to a famous unsolved problem in number theory: The distribution of the numbers $(3/2)^n$ modulo $1$. See here for a relatively recent paper that might contain additional references:

https://arxiv.org/abs/1806.03559

If there were a simple answer to your question this problem (and another famous one) would be nearer to solution, or would even be solved by now.

Answer 2

This is not a full answer, but too long to fit into a comment.

There is a way to compute a closed formula for the coefficients $c_i$ of the binary representation of $3^n = \sum_{i=0}^{m}{c_i2^i}$. However, the formula does not seem to exhibit regularity with increasing $i$ and also its complexity and computation time grows roughly exponentially with $i$. However, if $3^n \mod{2^k}$ up to a certain $k$ may help you, this is how to do it.

Thanks to Lucas's theorem we can represent $n$ as:

$$n = \sum_{j=0}^{q}{d_j2^j} =\sum_{j = 0}^{q}{\left[{n \choose 2^j}\mod{2}\right]2^j}$$

then:

$$3^n=3^{\sum_{j=0}^{q}{d_j2^j}}=\prod_{j=0}^{q}{3^{d_j2^j}}=\prod_{j=0}^{q}{\left(3^{2^j}\right)^{d_j}}$$

Each term of the product will be $1$ when $d_j = 0$ and $3^{2^j}$ when $d_j = 1$, thus we can compute the first powers of $3^{2^j} = \sum_{i=0}^{r}{e_i2^i}$ to get the following table:

$$ \begin{array}{c|lllllll} 3^{2^j} & e_0 & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 & e_7 & e_8 & \ldots \\ \hline 3^1 & 1 & 1 \\ 3^2 & 1 & 0 & 0 & 1 \\ 3^4 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 3^8 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & \ldots \\ 3^{16} & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & \ldots \\ \end{array} $$

and if $\left(3^{2^j}\right)^{d_j} = \sum_{i=0}^{r}{f_i2^i}$:

$$ \begin{array}{c|lllllll} \left(3^{2^j}\right)^{d_j} & f_0 & f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 & \ldots \\ \hline \left(3^1\right)^{d_0} & 1 & d_0 \\ \left(3^2\right)^{d_1} & 1 & 0 & 0 & d_1 \\ \left(3^4\right)^{d_2} & 1 & 0 & 0 & 0 & d_2 & 0 & d_2 \\ \left(3^8\right)^{d_3} & 1 & 0 & 0 & 0 & 0 & d_3 & 0 & d_3 & d_3 & \ldots \\ \left(3^{16}\right)^{d_4} & 1 & 0 & 0 & 0 & 0 & 0 & d_4 & 0 & d_4 & \ldots \\ \end{array} $$

where $f_0$ is always $1$ regardless of $d_j$.

Now we can start binary-multiplying the rows of the last table to obtain:

$$\left(3^1\right)^{d_0}\left(3^1\right)^{d_1}=1+2d_0+2^3d_1+2^4d_0d_1$$ $$\left(3^1\right)^{d_0}\left(3^1\right)^{d_1}\left(3^1\right)^{d_2}=1+2d_0+2^3d_1+2^4(d_0d_1+d_2 \mod 2)+2^5(d_0d_2+d_0d_1d_2 \mod 2)+2^6t$$

where we had a carry of $d_0d_1d_2 \mod 2$ at $2^5$, and finally:

$$\left(3^1\right)^{d_0}\left(3^1\right)^{d_1}\left(3^1\right)^{d_2}\left(3^1\right)^{d_3}=1+2d_0+2^3d_1+2^4(d_0d_1+d_2 \mod 2)+2^5(d_0d_2+d_0d_1d_2+d_3 \mod 2)+2^6u$$

and because when $j \gt 0$ we have $3^{2^{j+1}}-1=\left(3^{2^{j}}+1\right)\left(3^{2^{j}}-1\right)=2v\left(3^{2^{j}}-1\right)$ we know that $d_j$ will not appear before $f_{j+2}$.

Hence the first coefficients of $3^n = \sum_{i=0}^{m}{c_i2^i}$ are:

$$c_0=1$$ $$c_1=d_0={n \choose 1} \mod{2}$$ $$c_2=0$$ $$c_3=d_1={n \choose 2} \mod{2}$$ $$c_4=d_0d_1+d_2 \mod 2={n \choose 1}{n \choose 2}+{n \choose 4} \mod{2}={n \choose 3}+{n \choose 4} \mod{2}$$ $$c_5=d_0d_2+d_0d_1d_2+d_3 \mod 2={n \choose 1}{n \choose 4}+{n \choose 1}{n \choose 2}{n \choose 4}+{n \choose 8} \mod{2}={n \choose 5}+{n \choose 7}+{n \choose 8}\mod{2}$$

where we used again Lucas's theorem to simplify the products of binomial coefficients $\mod 2$.

Further coefficients could be computed with a program, but as said, the computation time and number of binomial coefficients grows quickly.