#LyX 2.4 created this file. For more info see https://www.lyx.org/ \lyxformat 620 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \begin_preamble \input defs \end_preamble \use_default_options true \maintain_unincluded_children no \language english \language_package default \inputencoding utf8 \fontencoding auto \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_roman_osf false \font_sans_osf false \font_typewriter_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \float_placement class \float_alignment class \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_formatted_ref 0 \use_minted 0 \use_lineno 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style english \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tablestyle default \tracking_changes false \output_changes false \change_bars false \postpone_fragile_content false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \docbook_table_output 0 \docbook_mathml_prefix 1 \end_header \begin_body \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc2[24] \end_layout \end_inset Consider the following four number systems: \end_layout \begin_layout Enumerate binary (signed magnitude); \end_layout \begin_layout Enumerate negabinary (radix \begin_inset Formula $-2$ \end_inset ); \end_layout \begin_layout Enumerate balanced ternary; and \end_layout \begin_layout Enumerate radix \begin_inset Formula $b=\frac{1}{10}$ \end_inset . \end_layout \begin_layout Standard Use each of these four number systems to express each of the following three numbers: \end_layout \begin_layout Enumerate \begin_inset Formula $-49$ \end_inset ; \end_layout \begin_layout Enumerate \begin_inset Formula $-3\frac{1}{7}$ \end_inset (show the repeating cycle); \end_layout \begin_layout Enumerate \begin_inset Formula $\pi$ \end_inset (to a few significant figures). \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset \end_layout \begin_layout Enumerate \begin_inset Formula $-49\to-110001$ \end_inset . Multiplying by 2, \begin_inset Formula $\frac{1}{7}\to\frac{2}{7}\to\frac{4}{7}\to1+\frac{1}{7}$ \end_inset , so \begin_inset Formula $-3\frac{1}{7}\to-11.\overbrace{001}$ \end_inset . Finally, \begin_inset Formula $\pi\to11.00100100001111...$ \end_inset \end_layout \begin_layout Enumerate The trick is to express the number in binary and, for the odd positions (the ones where \begin_inset Formula $(-2)^{k}$ \end_inset is negative), add 1 to the part of the number on the right, because we are subtracting \begin_inset Formula $2^{k}$ \end_inset instead of adding so we compensate for that. For negative numbers, we represent them in two's complement before this change, effectively adding \begin_inset Formula $2^{M}$ \end_inset for some large \begin_inset Formula $M$ \end_inset , and after it we drop that upper bit to subtract \begin_inset Formula $2^{M}$ \end_inset . Thus \begin_inset Formula $-49\to...111001111\to11010011$ \end_inset , \begin_inset Formula $-3\frac{1}{7}\to...1100.\overbrace{110110}\to1101.\overbrace{001011}$ \end_inset , \begin_inset Formula $\pi\to111.01100100010000...$ \end_inset . \end_layout \begin_layout Enumerate We proceed as in the text: \begin_inset Formula \begin{align*} -49 & \to-1211\to...11102200\to\overline{1}11\overline{1}\overline{1};\\ -3\frac{1}{7} & \to-10.\overbrace{010212}\to\dots1101.\overbrace{100122}\to\overline{1}0.\overbrace{0\overline{1}\overline{1}011};\\ \pi & \to10.010211012\dots\to...1121.122022201\dots\to10.011\overline{1}111\overline{1}0\dots. \end{align*} \end_inset \end_layout \begin_layout Enumerate This is like the decimal system but backwards, so \begin_inset Formula $-49\to-9.4$ \end_inset , \begin_inset Formula $-3\frac{1}{7}\to-\overbrace{758241}3$ \end_inset , \begin_inset Formula $\pi\to...51413$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash exerc5[00] \end_layout \end_inset Explain why a negative integer in nines' complement notation has a representation in ten's complement notation that is always one greater, if the representations are regarded as positive. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset Ten's complement of a negative number \begin_inset Formula $s$ \end_inset is \begin_inset Formula $10^{M}+s$ \end_inset , for a suitably large integer \begin_inset Formula $M$ \end_inset , while nines' complement is \begin_inset Formula $(10^{M}-1)+s$ \end_inset , so the ten's complement is one greater. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash exerc8[M10] \end_layout \end_inset Prove Eq. (5). \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset The part at the left is \begin_inset Formula $\sum_{j}a_{j}b^{j}$ \end_inset , while the part at the right is \begin_inset Formula $\sum_{j}A_{j}b^{kj}$ \end_inset , but \begin_inset Formula $A_{j}=\sum_{i=0}^{k-1}a_{kj+i}b^{i}$ \end_inset , so this is \begin_inset Formula \[ \sum_{j}A_{j}b^{kj}=\sum_{j}\sum_{i=0}^{k-1}(a_{kj+i}b^{i})b^{kj}=\sum_{j}\sum_{i=0}^{k-1}(a_{kj+i}b^{kj+i})=\sum_{j}a_{j}b^{j}. \] \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc9[15] \end_layout \end_inset Change the following \emph on octal \emph default numbers to \emph on hexadecimal \emph default notation, using the hexadecimal digits \family typewriter 0 \family default , \family typewriter 1 \family default , ..., \family typewriter 9 \family default , \family typewriter A \family default , \family typewriter B \family default , \family typewriter C \family default , \family typewriter D \family default , \family typewriter E \family default , \family typewriter F \family default : 12; 5655; 2550276; 76545336; 3726755. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset We use Eq. (5) with base 2. \end_layout \begin_layout Standard \align center \begin_inset Tabular \begin_inset Text \begin_layout Plain Layout Octal \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Binary \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Hexadecimal \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 12 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 010 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \family typewriter A \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 5655 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 101 110 101 101 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \family typewriter BAD \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 2550276 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 10 101 101 000 010 111 110 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \family typewriter AD0BE \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 76545336 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 111 110 101 100 101 011 011 110 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \family typewriter FACADE \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 3726755 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 11 111 010 110 111 101 101 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \family typewriter FADED \end_layout \end_inset \end_inset \end_layout \begin_layout Standard \begin_inset Note Comment status open \begin_layout Plain Layout Is this what academics do when they get bored? \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc13[M21] \end_layout \end_inset In the decimal system there are some numbers with two infinite decimal expansions; for example, \begin_inset Formula $2.3599999...=2.3600000...$ \end_inset . Does the \emph on negadecimal \emph default (base \begin_inset Formula $-10$ \end_inset ) system have unique expansions, or are there real numbers with two different infinite expansions in this base also? \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset There are real numbers with two different infinite expansions: \begin_inset Formula \[ \tfrac{1}{11}=0.090909...=(0.090909...)_{-10}=(1.909090...)_{-10}. \] \end_inset Effectively, \begin_inset Formula $(0.090909...)_{-10}=\sum_{k\geq1}9\cdot(-10)^{-2k}=9\sum_{k\geq1}100^{-k}=9\frac{\frac{1}{100}}{\frac{99}{100}}=\frac{1}{11}$ \end_inset , but \begin_inset Formula $(1.909090...)_{-10}=1+\sum_{k\geq1}9\cdot(-10)^{-2k+1}=1-90\sum_{k\geq1}100^{-k}=1-90\frac{1}{99}=1-\frac{10}{11}=\frac{1}{11}$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc19[23] \end_layout \end_inset (David W. Matula.) Let \begin_inset Formula $D$ \end_inset be a set of \begin_inset Formula $b$ \end_inset integers, containing exactly one solution to the congruence \begin_inset Formula $x\equiv j\pmod b$ \end_inset for \begin_inset Formula $0\leq j0$ \end_inset , then all numbers in \begin_inset Formula $D$ \end_inset are negative, but the integers between \begin_inset Formula $l$ \end_inset and \begin_inset Formula $u$ \end_inset are positive so they couldn't be represented in the given form, \begin_inset Formula $\#$ \end_inset and a similar thing would happen if \begin_inset Formula $u<0$ \end_inset . Now, in the algorithm above, \begin_inset Formula $q-k=\lfloor\frac{m}{b}\rfloor-k=\frac{m-r}{b}-\frac{x-r}{b}=\frac{m-x}{b}$ \end_inset . With this, if \begin_inset Formula $m>u$ \end_inset , then \begin_inset Formula $m(b-1)>-\min D$ \end_inset , but and therefore \begin_inset Formula \[ m-(q-k)=m-\frac{m-x}{b}=\frac{m(b-1)+x}{b}>\frac{-\min D+\min D}{b}=0, \] \end_inset so \begin_inset Formula $q-km-\frac{\max D}{b}\geq m+l, \] \end_inset so \begin_inset Formula $q-k\geq l$ \end_inset . This means that, on each step, \begin_inset Formula $m$ \end_inset is smaller by at least 1, but it doesn't become smaller than \begin_inset Formula $l$ \end_inset , so it eventually reaches the interval \begin_inset Formula $[l,u]$ \end_inset in at most \begin_inset Formula $|m-u|$ \end_inset steps. And if \begin_inset Formula $mm$ \end_inset , and \begin_inset Formula \[ m+(q-k)=\frac{m(b+1)-x}{b}0$ \end_inset , we take \begin_inset Formula $k\in\mathbb{N}$ \end_inset such that \begin_inset Formula $|2^{k}-n|$ \end_inset is minimum, write a 1 at position \begin_inset Formula $k$ \end_inset , and then write \begin_inset Formula $n-2^{k}$ \end_inset on the \begin_inset Formula $k$ \end_inset positions to the right. If \begin_inset Formula $n<0$ \end_inset , we do the same except that first we write \begin_inset Formula $\overline{1}$ \end_inset instead of 1. \end_layout \begin_layout Standard Now we prove that this in fact results in the representation fewest number of nonzero digits. We only need to prove it for positive \begin_inset Formula $n$ \end_inset . \end_layout \begin_layout Standard Now, if \begin_inset Formula $n=2^{k}$ \end_inset or \begin_inset Formula $3\cdot2^{k}$ \end_inset for some \begin_inset Formula $k\in\mathbb{N}$ \end_inset , the statement is trivial. Otherwise, if \begin_inset Formula $2^{k}2^{k-1}$ \end_inset , \begin_inset Formula $t$ \end_inset would need to have its most significant digit in position \begin_inset Formula $k$ \end_inset or \begin_inset Formula $k-1$ \end_inset , but any representation of \begin_inset Formula $t$ \end_inset that starts at position \begin_inset Formula $k$ \end_inset can be converted into one of \begin_inset Formula $2^{k}-n$ \end_inset by removing the 1 at that position, and any one starting at position \begin_inset Formula $k-1$ \end_inset can be converted into one of \begin_inset Formula $2^{k}-n$ \end_inset by swapping the sign in that position, so in general \begin_inset Formula $\sigma(t)=\sigma(2^{k+1}-n)\geq\sigma(2^{k}-n)=\sigma(n-2^{k})$ \end_inset . \end_layout \begin_layout Standard A similar argument shows that, if \begin_inset Formula $n>3\cdot2^{k-1}$ \end_inset , then \begin_inset Formula $\sigma(n-2^{k})\geq\sigma(2^{k+1}-n)$ \end_inset . \end_layout \end_body \end_document