Chapter 4

Evaluate each sum. $$\sum_{k=1}^{30}\left(3 k^{2}-1\right)$$

The binary representation of an integer can also be used to find its hexadecimal representation. Group the bits in fours from right to left and then replace each group with the equivalent hexadecimal digit. For instance, $$243=11110011_{\text {two }}=1111 \text { 0011 }_{\text {two }}=\mathrm{F} 3_{\text {sixteen }}$$ Using this method express each binary number in base 16. $$1110101_{\text {two }}$$

Let \(a \in \mathbf{Z}, S=\\{a, a+1, \ldots, T \subseteq S, \text { and } a \in T \text { . Let } k \text { be any element }\) of \(S\) such that whenever \(k \in T, k+1 \in T .\) Prove that \(S=T\) .

Evaluate each sum, where \(d\) is a positive integer. $$\sum_{d | 6} d$$

Let \(a \in \mathbf{Z}, S=\\{a, a+1, \ldots\\}, T \subseteq S,\) and \(a \in T .\) Let \(k\) be any element of \(S\) such that whenever \(k \in T, k+1 \in T .\) Prove that \(S=T\)

Evaluate each sum. $$\sum_{k=1}^{50}\left(k^{3}+2\right)$$

The binary representation of an integer can also be used to find its hexadecimal representation. Group the bits in fours from right to left and then replace each group with the equivalent hexadecimal digit. For instance, $$243=11110011_{\text {two }}=1111 \text { 0011 }_{\text {two }}=\mathrm{F} 3_{\text {sixteen }}$$ Using this method express each binary number in base 16. $$10110101_{\text {two }}$$

Let \(a \in \mathbf{Z}\) and \(S=\\{a, a+1, \ldots] .\) Let \(P(n)\) be a predicate on \(S\) such that the following conditions are satisfied: (1) \(\mathrm{P}(a)\) is true; \((2)\) If \(\mathrm{P}(a)\) \(\mathrm{P}(a+1), \ldots, \mathrm{P}(k)\) are true for any \(k \geq a,\) then \(\mathrm{P}(k+1)\) is also true. Prove that \(\mathrm{P}(n)\) is true for every \(n \geq a\)

Write an iterative algorithm to do the tasks. Determine if two \(n \times n\) matrices \(A\) and \(B\) are equal.

Evaluate each sum, where \(d\) is a positive integer. $$\sum_{d | 12} 1$$

The techniques explained in Exercises \(9-12\) are reversible; that is, the octal and hexadecimal representations of integers can be used to find their binary representations. For example, $$ 345_\mathrm{eight}=011100 \quad 101_{\mathrm{two}}=11100101_{\mathrm{two}} $$ Using this technique, rewrite each number in base two. $$ 36_{\text { sixteen }} $$

Verify each. $$\sum_{i=1}^{n} i(i+1)=\mathrm{O}\left(n^{3}\right)$$

Write an iterative algorithm to do the tasks. Compute the product of two \(n \times n\) matrices \(A\) and \(B\).

Evaluate each sum, where \(d\) is a positive integer. $$\sum_{d | 18}\left(\frac{1}{d}\right)$$

Let \(A=\left\langle a_{i j}\right)_{n \times n}\) and \(B=\left(b_{i j}\right)_{n \times n}\) \(A\) is less than or equal to \(B\) denoted by \(A \leq B,\) if \(a_{i j} \leq b_{i j}\) for every \(i\) and \(j .\) Write an algorithm to determine if \(A \leq B\)

The techniques explained in Exercises \(9-12\) are reversible; that is, the octal and hexadecimal representations of integers can be used to find their binary representations. For example, $$ 345_\mathrm{eight}=011100 \quad 101_{\mathrm{two}}=11100101_{\mathrm{two}} $$ Using this technique, rewrite each number in base two. $$ 237_{\text { eight }} $$

Write an iterative algorithm to do the tasks. Let \(A=\left(a_{i j}\right)_{n \times n}\) and \(B=\left(b_{i j}\right)_{n \times n} . A\) is less than or equal to \(B\) denoted by \(A \leq B,\) if \(a_{i j} \leq b_{i j}\) for every \(i\) and \(j .\) Write an algorithm to determine if \(A \leq B\).

Evaluate each sum, where \(d\) is a positive integer. $$\sum_{d | 18}\left(\frac{18}{d}\right)$$

Consider a list \(X\) of \(n\) numbers \(x_{1}, x_{2}, \ldots, x_{n} .\) Write iterative algorithms to do the tasks. Find the sum of the numbers.

The techniques explained in Exercises \(9-12\) are reversible; that is, the octal and hexadecimal representations of integers can be used to find their binary representations. For example, $$ 345_\mathrm{eight}=011100 \quad 101_{\mathrm{two}}=11100101_{\mathrm{two}} $$ Using this technique, rewrite each number in base two. $$ 237_{\text { sixteen }} $$

The techniques explained in Exercises \(9-12\) are reversible; that is, the octal and hexadecimal representations of integers can be used to find their binary representations. For example, $$ 345_\mathrm{eight}=011100 \quad 101_{\mathrm{two}}=11100101_{\mathrm{two}} $$ Using this technique, rewrite each number in base two. $$ 3 \mathrm{AD}_{\text { sixteen }} $$

Consider a list \(X\) of \(n\) numbers \(x_{1}, x_{2}, \ldots, x_{n} .\) Write iterative algorithms to do the tasks. Find the product of the numbers.

Consider a list \(X\) of \(n\) numbers \(x_{1}, x_{2}, \ldots, x_{n} .\) Write iterative algorithms to do the tasks. Find the maximum of the numbers.

In Exercises \(21-28,\) perform the indicated operations. $$ \begin{array}{r}{1111_{\mathrm{two}}} \\ {+1011_\mathrm{two}}\end{array} $$

(Easter Sunday) Here is a second method" for determining Easter Sunday in a given year \(N .\) Let \(a=N\) mod \(19, b=N\) div \(100, c=N\) mod 100 \(d=b \operatorname{div} 4, e=b \bmod 4, f=(b+8) \operatorname{div} 25, g=(b-f+1) \operatorname{div} 3, h=(19 a+\) \(b-d-g+15) \bmod 30, i=c \operatorname{div} 4, j=c \bmod 4, k=(32+2 e+2 i-h-j)\) \(\bmod 7, \ell=(a+11 h+22 k) \operatorname{div} 451, m=(h+k-7 \ell+114) \operatorname{div} 31,\) and \(n=(h+k-7 \ell+114)\) mod \(31 .\) Then Easter Sunday falls on the \((n+1)\) st day of the \(m\) th month of the year. Compute the date for Easter Sunday in each year. $$2000$$

Perform the indicated operations. $$\begin{aligned}&1111_{\text {two }}\\\&+1011_{\text {two }}\end{aligned}$$

Consider a list \(X\) of \(n\) numbers \(x_{1}, x_{2}, \ldots, x_{n} .\) Write iterative algorithms to do the tasks. Find the minimum of the numbers.

In Exercises \(21-28,\) perform the indicated operations. $$ \begin{aligned} & 1076 _\mathrm{eight} \\\\+& 2076_ \mathrm{eight} \end{aligned} $$

(Easter Sunday) Here is a second method" for determining Easter Sunday in a given year \(N .\) Let \(a=N\) mod \(19, b=N\) div \(100, c=N\) mod 100 \(d=b \operatorname{div} 4, e=b \bmod 4, f=(b+8) \operatorname{div} 25, g=(b-f+1) \operatorname{div} 3, h=(19 a+\) \(b-d-g+15) \bmod 30, i=c \operatorname{div} 4, j=c \bmod 4, k=(32+2 e+2 i-h-j)\) \(\bmod 7, \ell=(a+11 h+22 k) \operatorname{div} 451, m=(h+k-7 \ell+114) \operatorname{div} 31,\) and \(n=(h+k-7 \ell+114)\) mod \(31 .\) Then Easter Sunday falls on the \((n+1)\) st day of the \(m\) th month of the year. Compute the date for Easter Sunday in each year. $$2076$$

Perform the indicated operations. 1076 eight \(+2076_{\text {eight }}\)

In Exercises \(21-28,\) perform the indicated operations. $$ \begin{aligned} & 3076_{\text { sixteen }} \\\\+& 5776_{\text { sixteen }} \end{aligned} $$

Consider a list \(X\) of \(n\) numbers \(x_{1}, x_{2}, \ldots, x_{n} .\) Write iterative algorithms to do the tasks. Print the numbers in the given order \(x_{1}, x_{2}, \ldots, x_{n}\).

(Easter Sunday) Here is a second method" for determining Easter Sunday in a given year \(N .\) Let \(a=N\) mod \(19, b=N\) div \(100, c=N\) mod 100 \(d=b \operatorname{div} 4, e=b \bmod 4, f=(b+8) \operatorname{div} 25, g=(b-f+1) \operatorname{div} 3, h=(19 a+\) \(b-d-g+15) \bmod 30, i=c \operatorname{div} 4, j=c \bmod 4, k=(32+2 e+2 i-h-j)\) \(\bmod 7, \ell=(a+11 h+22 k) \operatorname{div} 451, m=(h+k-7 \ell+114) \operatorname{div} 31,\) and \(n=(h+k-7 \ell+114)\) mod \(31 .\) Then Easter Sunday falls on the \((n+1)\) st day of the \(m\) th month of the year. Compute the date for Easter Sunday in each year. $$3000$$

Perform the indicated operations. \(3076_{\text {sixteen }}\) \(+5776_{\text {sixteen }}\)

Evaluate each sum and product. $$\sum_{i=1}^{n} \sum_{j=1}^{i} j^{2}$$

In Exercises \(21-28,\) perform the indicated operations. $$ \begin{array}{r}{101101_{\mathrm{two}}} \\ {-10011_{\mathrm{two}}}\end{array} $$

Perform the indicated operations. \(101101_{\text {two }}\) \(-10011_{\text {two }}\)

Evaluate each sum and product. $$\sum_{i=1}^{n} \sum_{j=1}^{i}(2 j-1)$$

In Exercises \(21-28,\) perform the indicated operations. $$ \begin{array}{r}{11000_{\text { two }}} \\ {-\quad 100_{\text { two }}}\end{array} $$

Perform the indicated operations. \(11000_{\text {two }}\) \(-\quad 100_{\mathrm{two}}\)

In Exercises \(21-28,\) perform the indicated operations. $$ \begin{array}{r}{10111_{\mathrm{tw} 0}} \\ { \times 1101_{\mathrm{two}}}\end{array} $$

Euler's phi-function \(\varphi\) is another important number-theoretic function on \(\mathbb{N},\) defined by \(\varphi(n)=\) number of positive integers \(\leq n\) and relatively prime to \(n .\) For example, \(\varphi(1)=1=\varphi(\mathbf{2}), \varphi(3)=\mathbf{2}=\varphi(4),\) and \(\varphi(5)=4 .\) Evaluate \(\varphi(n)\) for each value of \(n\). $$15$$

Perform the indicated operations. \(10111_{\text {two }}\) \(\times 1101_{\text {two }}\)

In Exercises \(21-28,\) perform the indicated operations. $$ \begin{array}{r}{1024_ \text { eight }} \\ { \times 2776_ \text { eight }}\end{array} $$

Euler's phi-function \(\varphi\) is another important number-theoretic function on \(\mathbb{N},\) defined by \(\varphi(n)=\) number of positive integers \(\leq n\) and relatively prime to \(n .\) For example, \(\varphi(1)=1=\varphi(\mathbf{2}), \varphi(3)=\mathbf{2}=\varphi(4),\) and \(\varphi(5)=4 .\) Evaluate \(\varphi(n)\) for each value of \(n\). $$17$$

Perform the indicated operations. \(1024_{\text {eight }}\) \(\times 2776_{\text {eight }}\)

In Exercises \(21-28,\) perform the indicated operations. $$ \begin{aligned} & 3 \mathrm{ABC}_{\text { sixteen }} \\ \times & 4 C B A_{\text { sixteen }} \end{aligned} $$

Arrange the binary numbers \(1011,110,11011,10110,\) and 101010 in order of increasing magnitude.

Compute \(\sum_{d | n} \varphi(d)\) for \(n=5,6,10,\) and 12.

A magie square of order \(n\) is a square arrangement of the positive integers 1 through \(n^{2}\) such that the sum of the integers along each row, column, and diagonal is a constant \(k\) , called the magie constant. Figure 4.30 shows two magic squares, one of order 3 and the other of order \(4 .\) Prove that the magic constant of a magic square of order \(n\) is \(n\left(n^{2}+1\right) / 2 .\)