Represent every Natural number as a summation/subtraction of distinct power of 3

I have seen this in a riddle where you have to chose 4 weights to calculate any weight from 1 to 40kgs. Some examples,

$$8 = {3}^{2} - {3}^{0}$$ $$12 = {3}^{2} + {3}^{1}$$ $$13 = {3}^{2} + {3}^{1}+ {3}^{0}$$ Later I found its also possible to use only 5 weights to calculate any weight between 1-121. $$100 = {3}^{4} + {3}^{3} - {3}^{2} + {3}^{0}$$ $$121 = {3}^{4} + {3}^{3} + {3}^{2} + {3}^{1} + {3}^{0}$$

Note: It allows negative numbers too. how I represent 8 and 100.

I want to know if any natural number can be represented as a summation of power of 3. I know this is true for 2. But is it really true for 3? What about the other numbers? Say $4, 5, 6, ... $

Solution 1:

You can represent any number $n$ as $a_k 3^k + a_{k-1} 3^{k-1} + \dots + a_1 3 + a_0$, where $a_i \in \{-1,0,1\}$. This is called balanced ternary system, and as Wikipedia says, one way to get balanced ternary from normal ternary is to add ..1111 to the number (formally) with carry, and then subtract ..1111 without carry. For a generalization, see here.

Solution 2:

It’s trivial to write any positive integer as a sum of powers of $3$ if you allow repetitions; you really meant to ask about writing positive integers as sums of distinct powers of $3$. It is not possible to write every positive integer in that way: you clearly cannot write $2$ as the sum of distinct powers of $3$.

In order to use the weights $1,3,9$, and $27$ kg to weigh every whole number amount from $1$ through $40$ kg, you must be using a two-pan balance, and you must allow the weights to be placed in either pan. The scales balance when the weight of the object plus the weights in its pan equal the total of the weights in the other pan. Thus, to weigh a $5$ kg object, for instance, you must put the $1$ and $3$ kg weights in the same pan as the object and the $9$ kg weight in the other pan. The scales then balance, because $5+1+3=9$. Equivalently, $$5=9-3-1=3^2-3^1-3^0\;.$$ Thus, it’s not a matter of writing $5$ as a sum of distinct powers of $3$: we write it as a sum or difference of distinct powers of $3$.

This is indeed always possible. (Indeed, it is possible to write every integer as a sum or difference of distinct powers of $3$.) For example, $19=3^3-3^2+3^0$. We could abbreviate this to +-0+, where the plus sign indicates that we add the power, the zero indicates that we don’t use it at all, and the minus sign indicates that we subtract it. The resulting positional notation for integers is called balanced ternary notation, and you can find quite a lot on it on the web. This PDF gives a reasonable introduction.

Solution 3:

You can do it if you want to have $\pm 1,0$ as coefficients. It is known you can do it with coefficients $\{0,1,2\}$ (namely the base $3$ representation). Once you have done this: Say $$k=c_03^0+c_13^1+...+c_n3^n$$If $c_1=0$ or $1$, then leave it, and move to the next one. Say $c_k=2$, then change $c_k$ for $-1$ and then replace $c_{k+1}$ for $c_{k+1}+1$. Note that the summation remains unchanged because $2\cdot 3^k+c_{k+1}3^{k+1}=2\cdot 3^k+3c_{k+1}3^k$ and if we do the replacement you get $-3^k+(c_{k+1}+1)3^{k+1}$, which is the same quantity.

Now if $c_{k+1}$ is equal to $3$, then you replace it for $0$ and then replace $c_{k+2}$ by $c_{k+2}+1$. With this algorithm you can arrive at the number written only with $\pm 1,0$ as the coefficients of powers of three.

This does not generalizes, because underlying we use the fact that $2\equiv -1\pmod{3}$.