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

-
I am not a student of mathematics but a math enthusiast. Pardon me for any mistakes. Specially for terminology and wrong tagging. –  Shiplu Mar 13 '12 at 7:51
How do you do $2$? $3^1-3^0$ or $2\cdot 3^0$ ? –  Raskolnikov Mar 13 '12 at 7:56
Not every positive integer is a sum of powers of 3 without repetiton, for example 7 isn't. if you allow repetitions, you can write every positive integer as a sum of powers of 3, with no power of 3 repeated more than twice ( eg 7 = 1 + 3 + 3). If you know about proof by induction, you can prove it that way. If not, the recipe is to keep subtracting the biggest power of 3 you can (still leaving a non-negative remainder) : For example if n = 173, subtract 81, then subtract 81 again, leaving 11. Then subtract 9, then 1, then 1: so 173 = 81+81+ 9+ 1+ 1. –  Geoff Robinson Mar 13 '12 at 8:00
As examples in Isaac's answer suggests, it is not always possible if don't allow repitions. But what is true is, any number can be written as sum of various powers of two with coefficients from $0,1,2$ which is what goes behind allowing repitions. Further note that, this is nothing new. In the decimal number system, any number can be written as sum of powers of 10 with coefficients from $\{0,1,\cdots,9\}$. –  user21436 Mar 13 '12 at 8:01
OK, then it clearly can be done, by replacing $2.3^{k}$ by $3^{k+1} - 3^{k}$ whenever it occurs in the representation I describe. –  Geoff Robinson Mar 13 '12 at 8:05

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.

-

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.

-
I have updated my question title to include distinct –  Shiplu Mar 13 '12 at 8:17

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

-
Damn, I didnt see people had answered. :/ –  Daniel Montealegre Mar 13 '12 at 8:15

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

-