Negabinary Numbers

Number Theory Level 5

$\Large 20_{10} = 10100_2 = 10100_{-2}$

Today, modern mathematics uses what is known as the decimal number system to write out large numbers. This means that when we write our numbers, we do so by thinking in powers of $10$ . For example, the number $234$ is really $2\times10^2+3\times10^1+4\times10^0$ .

While the number $10$ is the norm used around the world, numbers can really be written in any base. Take our example of $234$ from above. It can be written as $4\times7^2+5\times7^1+3\times7^0$ , meaning that it's base $7$ representation is $453_7$ . The subscript $7$ denotes that the number is not in base 10, as to avoid confusion.

Not only can numbers be written in positive bases, but in negative bases as well! The example that can be seen at the top of the problem shows the conversion of the number $20$ to Base $2$ , known as binary , and Base $-2$ , known as negabinary . As you can see, its representation is the same in both bases, but this is not the case with all numbers. For example, $7=111_2=11011_{-2}$ . How many positive integers $n<1000$ have the same representation in both binary and negabinary?

The answer is 31.

3 solutions

Dan Wilhelm
Jul 25, 2015

We are asked how many positive integers $n < 1000_{10} = 1111101000_2$ have equivalent binary and negabinary representations. We can represent each of these numbers as a 10-bit sequence $N = \{n_9, n_8, ..., n_0\}$ , where $n_i \in \{0,1\}$ . We define the binary representation of $N$ and the negabinary representation of $N$ respectively as follows:

$\sum\limits_{i=0}^9{n_i\cdot2^i}$ , and $\sum\limits_{i=0}^9{n_i\cdot(-2)^i}$ .

Let $a \in \mathbf{N}$ . When $i = 2a$ is even, each negabinary term is equivalent to the binary term, since $(-2)^{2a} = 4^a = 2^{2a}$ . When $i = 2a + 1$ is odd, the negabinary term is the additive inverse of the binary term, since $(-2)^{2a+1} = -2\cdot2^{2a} = -(2^{2a+1})$ . Hence, for a particular sequence $N$ , the negabinary representation is equivalent only when each odd bit is $0$ ; otherwise, it is less than the binary representation.

Since each odd bit must be $0$ , we are left with five bits that can be either $0$ or $1$ : $\{n_0, n_2, n_4, n_6, n_8\}$ . So, there are $2^5 = 32$ unique sequences. Excluding zero, there are $2^5 - 1 = 31$ equivalent representations.

Great job, this was the intended solution.

Garrett Clarke - 5 years, 10 months ago

But sir, some natural numbers do include zero.

Kenny Lau - 5 years, 10 months ago

I've edited the question to say "positive integers" rather than "natural numbers" to avoid confusion. Thank you!

Garrett Clarke - 5 years, 10 months ago

Amended the solution to clarify the wording "natural number". I agree with Kenny, the problem would benefit from being more explicit, e.g. $n$ is an integer such that $0 < n < 1000$ .

Dan Wilhelm - 5 years, 10 months ago

@Dan Wilhelm – Well, I firstly inputted 32, thought a long while, couldn't find any mistakes, but tried 16 either way, and then guessed 31 because maybe there are some special cases, and then got it right.

Kenny Lau - 5 years, 10 months ago

You need to show that all numbers in the form $\overline{n_8 0 n_6 0 n_4 0 n_2 0 n_0}_2$ are less than $1000$ (so they are counted). Had the problem state something like $n < 300$ instead, some of the numbers wouldn't be counted (for example $320 = 101000000_2 = 101000000_{-2}$ is no longer counted).

Ivan Koswara - 5 years, 10 months ago

Kenny Lau
Jul 25, 2015

$10100_2$ is really $1\times2^4 + 0\times2^3 + 1\times2^2 + 0\times2^1 + 0\times2^0$ .
$10100_{-2}$ is really $1\times(-2)^4 + 0\times(-2)^3 + 1\times(-2)^2 + 0\times(-2)^1 + 0\times(-2)^0$ .
Notice how $(-2)^4=2^4$ and $(-2)^3=-2^3$ .
Conclude that if the power is even, it is unchanged. If the power is odd, it is decreased.
Therefore, the only digits with "1" must be of even power.
$999_{10}=11\ 1110\ 0111_2$
The next smaller number with only even powers is:
$341_{10}=01\ 0101\ 0101_2$
There are only 5 digits that we can change, which is the five "1"s in the binary notation of $341_{10}$ .
Each of those 5 digits can either be $0$ or $1$ , giving us $2$ choices.
Multiplying them together gives $2\times2\times2\times2\times2=2^5=32$ .
$00\ 0000\ 0000_2=0_{10}$ and is not included, leaving us with $32-1=\fbox{31}$ numbers.

Ossama Ismail
Jul 29, 2018

Only the bits in the even locations will contribute to the solution. These bits are bits 0,2,4,6,8. Max no. that can be written in these 5 bits is = 341.

So, there are only Five bits that satisfy the required condition of this problem, and the solution is $2^5 -1 = 31$ .

Negabinary Numbers

The answer is 31.

3 solutions

0 pending reports