Prove or disprove that every real number has a unique negabinary representation

216 Views Asked by At

I've convinved myself that negabinary representations of $\Bbb R$ are exhaustive and unique. Can it be proven?

Of course the (relatively minor) problem occurs in conventional base $2$ that $0\overline1=1\overline0$ and therefore there are two representations for many numbers. But that appears not to be replicated in negabinary numbers.


Conventionally the negabinary numbers give unique representations of any given integer $n$ in base $-2$, i.e.:

$$n=\sum_{k=0}^\infty (-2)^ki_k:i\in\{0,1\}$$

Then e.g.

$1000_{-2}=(-2)^3+0+0+0=-8$, and

$10010_{-2}=(-2)^4+0+0+(-2)^1+0=14$.

One way of looking at this, is that every negabinary is the sum of a positive number drawn from the set:

$$\sum_{k=0}^\infty (2)^{2k}i_k:i\in\{0,1\}$$

and a negative number drawn from the set

$$-\sum_{k=0}^\infty (2)^{2k+1}i_k:i\in\{0,1\}$$


We can quickly say e.g. $0.1_{-2}=-\frac12$ and $0.11_{-2}=-\frac14$ but I'm unclear on how infinitely repeating fractions might be treated and whether every number has a (unique) representation.

The largest positive fraction we can write is $1/4+1/16+...=1/3$

and the smallest negative fraction we can write is $-1/2-1/8\ldots=-2/3$

The ability to express numbers in the range $1/3,-2/3$ fits perfectly with the effect of a bit-shift which multiplies by $-2$ so I believe every number is represented.

But what about on the question of whether representations are unique?

e.g. $01_{-2}=1/4\neq3/32=0.00\overline1_{-2}$

Therefore I'm sure a) every real number is represented, and b) no number can have multiple representations as in the binary case. Can this be proven?

2

There are 2 best solutions below

1
On BEST ANSWER

I don't think you have uniqueness. For example:

$.\overline{01}=\frac14+\frac{1}{16}+...=\frac13$; and

$1.\overline{10}=1-\frac12-\frac18-...=1-\frac23=\frac13$

1
On

$1 = \frac 1 2 + \frac 1 4 + \frac 1 8 + \frac 1 {16} + \frac 1 {32} + \frac 1 {64} + \dots$

so $1 - \frac 1 2 - \frac 1 8 - \frac 1 {32} - \dots= \frac 1 4 + \frac 1 {16} + \frac 1 {64} + \dots$

so $1.10101 \dots_{-2} = 0.0101 \dots_{-2} = \frac 1 3$