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

Question

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, ... $

Answer 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.

Answer 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.

Answer 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}$.

Answer 4

As requested, I write up an answer along the lines of my comments, although it is much the same as Daniel's answer: Given any positive integer $n,$ subtract the highest possible power of $3$ from $n$ which leaves a non-negative remainder, then repeat until zero is eventually reached.This expresses $n$ as a sum of powers of $3$ in which no power is repeated more than twice (the standard ternary representation of $n$). Then (starting from the left) replace $2.3^{k}$ by $3^{k+1} - 3^k$ whenever $3^k$ appears twice (this may disturb the coefficient of $3^{k+1},$ which would have previously been been $0,1$ or $-1$ since we started from the left. If it was previously $1$ then we have to adjust accordingly, moving left again). At the end, we will have written $n$ as a "sum" of powers of $3$ in which every power of $3$ which actually appears appears with coefficient $\pm 1.$ An illustrative example is $41 = 27 + 9 + 3 + 1+ 1.$ This can be rewritten as $27 +9 + 3 + (3-1) = 27 + 9 + (9-3) - 1 = 27 + 27 -9 -3 -1$ = $81 - 27 -9 -3-1.$