# What is the number of positive integers?

b. In a system of ternary (Base 3) number, with n digits, how many number can be represented? Answer:

c. For an n-digit signed 3's complement ternary number (n > 1), what is the number of positive integers?
Answer:

d. For an n-digit signed 3's complement ternary number (n > 1), how many zeros are there? Answer:

e. For a 4-digit signed 3's complement ternary number, what is the representation of -3?
Answer:

Thanks in advance.

-
There are $\aleph_0$ integers in any base or representation. Is there a maximum length or something? –  Robert Mastragostino Sep 17 '12 at 3:06
@Robert: $n$-digit. –  Brian M. Scott Sep 17 '12 at 3:06
You should tell us your attempts. Then maybe you will get some help. –  GEdgar Sep 17 '12 at 3:17
It looks as if you just copied the questions directly from an exam sheet, which is not a good practice. I think you would be more likely to receive some support if you rephrased it as a question you might actually ask a friend, rather than one that a teacher might assing to a student. It would also be helpful if you explainded what are your problems with the questions, and what you know already. –  Feanor Sep 22 '12 at 8:42

## 1 Answer

For (b), there are three possible choices for each digit, $0,1$, and $2$, and there are $n$ digits. When $n=1$ you get $0,1$, and $2$, or $3$ possible numbers. When $n=2$ you can take any of those three numbers and take any of the three digits onto the end of it:

\begin{align*} &00\qquad01\qquad02\\ &10\qquad11\qquad12\\ &20\qquad21\qquad22 \end{align*}

That’s $3\cdot3=3^2=9$ possibilities. With $3$ digits you could tack $0,1$, or $2$ on the end of any of those nine numbers to get a total of $9\cdot3=3^2\cdot3=3^3$ numbers. Now generalize.

Added: To answer (c)-(e), you simply have to understand exactly how signed $3$’s complement ternary notation works. To find the $n$-digit representation of an integer, first write out the absolute value of the integer in ordinary ternary notation, using $n-1$ digits. For instance, if $n=6$, $34$ is $01021_3$. Then add a leading sign digit, $0$ for a positive number or $0$ and $2$ for a negative number. At this stage $34$ yields $001021$, and $-34$ yields $201021$. Now subtract from $3^n$ as if these were ordinary positive integers written in ternary: doing everything in the ternary system, we get

      1000000            1000000
- 001021           - 201021
-------            -------
221202             021202


The $6$-digit signed $3$’s complement ternary representations of $34$ and $-34$ are therefore $221202$ and $021202$, respectively. In the case of $0$ this procedure yields $1000000$, which has one digit too many; just throw away the leading $1$ and keep $000000$.

A shortcut for the subtraction step is to replace each digit by its $2$’s complement and then add $1$; e.g., the $2$’s complement of $201021$ is $021201$, and adding $1$ in ternary yields $021202$. If a carry gives you an extra digit on the left, throw it away.

If you examine this procedure closely, you’ll see that the signed $3$’s-complement representation of a positive integer or $0$ always begins with $0$, and that of a negative integer with $1$. The remaining $n-1$ digits can all be any of the digits $0,1$, and $2$, except that we never get a $2$ followed by $n-1$ zeroes. For example, with $n=6$ we never get $200000$: if $200000=1000000-x$, then $x=100000$, with a sign bit of $1$, which is impossible.

You now have all of the necessary pieces. There is only one representation of $0$; what is it? I’ve worked an example that you can use as a model for answering (e). For (c), notice that the positive integers are those whose $n$-digit signed $3$’s-complement ternary representations begin with $0$ and have at least one non-zero digit. From part (a) you know how many $(n-1)$-digit ternary numbers there are. Throw away the one that’s all zeroes, and how many are left to represent positive integers?

-
Here, I fixed the problem. :( –  David Sep 17 '12 at 3:28