Determining if $m$ can be written as a combination of distinct powers of $w$.

Question

Given a weight $m$ and weights $w^0, w^1, w^2, \ldots, w^{100}$, determine if $m$ can be measured on a balance using these weights. In other words, is it possible to place a weight $m$ and some weights on the left pan of a scale, and some other weights on the right pan of the scale such that the pans of the scale were in balance?

This is an interesting question I found in my book.

I tried to convert $m$ into base $w$. If all bits are $0$ or $1$, then we can simply place the weight $m$ on the left side, and the corresponding weights on the right side of the scale.

But how do we solve the other case? (The case where we can have some masses on the left side of the scale)

Answer 1

Depending on which side of the scale some $w^k$ is (or is not), your number is represented as:

$$ m=\sum_{k=0}^{100}\delta\cdot w^k,\text{ }\delta\in\{-1,0,1\} $$

This is possible if and only if number $m$ has only digits $\{-1,0,1\}$ in "offset number base $\overline{w}$".

We define the "offset number base $\overline{w}$" as a base with digits $\{-1,0,1,2,3\dots,w-2\}$.

In comparison, a "standard number base $w$" has digits $\{0,1,2,3,4,\dots,w-1\}$.

Let $(-1)=\overline{1}$ be a notation for our negative one digit.

---

How to convert a number to base $\overline{w}$?

Notice that the digits of $m$ in base $w$ are simply the remainders of division of $m$ by $w$.

To get $\overline{w}$ digits instead of $w$ digits, simply treat the remainder $m\equiv(w-1)$ as $m\equiv(-1)$ instead, where we can write $(-1)=\overline1$.

To get the first digit, observe $m\pmod{w}=m_1\in\{0,1,2,\dots,w-1\}$ where $(w-1)\equiv(-1)$.

Now repeat the process on $(m-m_1)/w$ to get the second digit $m_2$, and so on.

---

For example,

Lets convert the number $m=293$ to "offset base" $\overline{w}$ for $w=7$.

$293\pmod7\equiv 6\equiv -1$ so the units digit is $m_1=-1$. The next number is $(293-\overline{1})/7=42$.

$42\pmod7\equiv 0$ so the next digit is $m_2=0$. The next number is $(42-0)/7=6$.

$6\pmod7\equiv 6\equiv -1$ so the next digit is $m_3=-1$. The next number is $(6-\overline{1})/7=1$.

$1\pmod7\equiv 1$ so the next digit is $m_4=1$. The next number is $0$, so we are done.

We got that $293$ has digits $(1,\overline1,0,\overline1)=(1,-1,0,-1)$ in base $\overline{w}=\overline7$, hence it is possible.

---

Remark. For $w=3$ this is also called Balanced ternary. - see Find algorithm for converting number to Balanced ternary.

Answer 2

Here is an algorithm that avoids actually converting to base $w$, although it accomplishes the same result. It involves serially looking at $m$ or a number derived from $m$ according to the modulus $w$.

Create a list with three categories: positive, discard, negative.

Compute $m \bmod w$. If that residue is other than $-1,0,1$, stop. The problem has no solution. If the residue is $-1$, write $w^0$ in the negative category. If the residue is $0$, write $w^0$ in the discard category. If the residue is $1$, write $w^0$ in the positive category.

Compute $m_1=\frac{m-(m \bmod w)}{w}$, and compute $m_1 \bmod w$. If that residue is other than $-1,0,1$, stop. The problem has no solution. If the residue is $-1$, write $w^1$ in the negative category. If the residue is $0$, write $w^1$ in the discard category. If the residue is $1$, write $w^1$ in the positive category.

Compute $m_2=\frac{m_1-(m_1 \bmod w)}{w}$, and compute $m_2 \bmod w$.

Continue as before, placing $w^k$ in a category according to the residue of $m_k$, if you do not encounter a stop at some step. Terminate the algorithm when ${m_k-(m_k \bmod w)}=0$

If we call numbers in the negative category $w^j$ and numbers in the positive category $w^i$, it will be true that $m=\sum(w^i)-\sum(w^j)$, so $m$ can be balanced using the set of weights $\{w^i,w^j\}$