Chapter 4

Express each decimal number as required. $$1776=(\quad)_{\text {eight }}$$

Find the set of possible remainders when an integer is divided by the given integer. Two

Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. $$\sum_{i=1}^{n} i^{3}=\left[\frac{n(n+1)}{2}\right]^{2}$$

Using the euclidean algorithm, find the gcd of the given integers. $$2076,1076$$

Using the big-oh notation, estimate the growth of each function. $$f(n)=23$$

(Twelve Days of Christmas) Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. $$ \sum_{i=1}^{n} a r^{i-1}=\frac{a\left(r^{n}-1\right)}{r-1}(r \neq 1) $$

Algorithm 4.13 finds the maximum value in a list \(X\) of \(n\) items. Use it to answer Exercises. Algorithm find max \((X, n, \max )\) (* This algorithm returns the largest item in a list \(x\) of \(n\) items in a variable called max. *) 0\. Begin (* algorithm *) 1\. \(\max \leftarrow x_{1}\) (* initialize max *) 2\. \(i \leftarrow 2\) 3\. while \(1 \leq n \mathrm{do}\) 4\. begin (* while *) 5\. if \(x_{1}>\) nax then (*update max *) 6\. \(\max \leftarrow x_{1}\) 7\. \(i \leftarrow i+1\) 8\. end while 9\. End (*algorithm *) Establish the correctness of the algorithm.

Express each decimal number as required. $$2076=(\quad)_{\text {sixteen }}$$

Find the set of possible remainders when an integer is divided by the given integer. Five

Using the euclidean algorithm, find the gcd of the given integers. $$2076,1776$$

Using the big-oh notation, estimate the growth of each function. $$f(n)=\sum_{k=1}^{n} k^{2}$$

(Twelve Days of Christmas) Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. \(n^{2}+n\) is divisible by 2

Algorithm 4.13 finds the maximum value in a list \(X\) of \(n\) items. Use it to answer Exercises. Algorithm find max \((X, n, \max )\) (* This algorithm returns the largest item in a list \(x\) of \(n\) items in a variable called max. *) 0\. Begin (* algorithm *) 1\. \(\max \leftarrow x_{1}\) (* initialize max *) 2\. \(i \leftarrow 2\) 3\. while \(1 \leq n \mathrm{do}\) 4\. begin (* while *) 5\. if \(x_{1}>\) nax then (*update max *) 6\. \(\max \leftarrow x_{1}\) 7\. \(i \leftarrow i+1\) 8\. end while 9\. End (*algorithm *) Let \(c_{n}\) denote the number of comparisons needed in line 5 . Show that \(c_{n}=O(n) .\)

The binary representation of an integer can conveniently be used to find its octal representation. Group the bits in threes from right to left and replace each group with the corresponding octal digit. For example, $$243=11110011_{\text {two }}=011 \quad 110 \quad 011_{\text {two }}=363_{\text {eight }}$$'Using this short cut, rewrite each binary number as an octal integer. $$1101_{\text {two }}$$

Find the set of possible remainders when an integer is divided by the given integer. Seven

Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. \(n^{2}+n\) is divisible by 2.

Using the euclidean algorithm, find the gcd of the given integers. $$3076,1976$$

Using the big-oh notation, estimate the growth of each function. $$f(n)=\sum_{k=1}^{n} k^{3}$$

(Twelve Days of Christmas) Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. \(n^{4}+2 n^{3}+n^{2}\) is divisible by 4

The binary representation of an integer can conveniently be used to find its octal representation. Group the bits in threes from right to left and replace each group with the corresponding octal digit. For example, $$243=11110011_{\text {two }}=011 \quad 110 \quad 011_{\text {two }}=363_{\text {eight }}$$'Using this short cut, rewrite each binary number as an octal integer. 11011 two

Find the set of possible remainders when an integer is divided by the given integer. Twelve

Let \(c_{n}\) denote the number of element-comparisons in line 6 of the insertion sort algorithm in Algorithm \(4.12 .\) Show that \(c_{n}=O\left(n^{2}\right)\)

In Exercises \(10-13,\) express the gcd of the given integers as a linear combination of them. $$12,9$$

Using the big-oh notation, estimate the growth of each function. $$f(n)=\sum_{i=1}^{n}\lfloor i / 2\rfloor$$

The number of lines formed by joining \(n( \geq 2)\) distinct points in a plane, no three of which being collinear, is \(n(n-1) / 2\)

Use the minmax algorithm in Algorithm 4.14 to answer Exercises. Algorithm iterative minmax \((X, n, min, m a x)\) (* This algorithm returns the minimum and the maximum of a list \(X\) of n elements. *) 0\. Begin (* algorithm *) 1\. If \(n \geq 1\) then 2\. begin (* if *) 3\. \(\min -x_{1}\) 4\. \(\max \leftarrow x_{1}\) 5\. for \(i=2\) to \(n\) do 6\. begin (* for *) 7\. if \(x_{1}<\) m i n then 8\. \(\min \leftarrow x_{1}\) 9\. if \(x_{1}>\) max then 10\. \(\max \leftarrow x_{1}\) 11\. endfor 12\. endif 13\. End (* algorithm *) Find the maximum and the minimum of the list \(12,23,6,2,19,15,\) \(37 .\)

Sort the following lists using the bubble sort algorithm. 23,7,18,19,53

The binary representation of an integer can conveniently be used to find its octal representation. Group the bits in threes from right to left and replace each group with the corresponding octal digit. For example, $$243=11110011_{\text {two }}=011 \quad 110 \quad 011_{\text {two }}=363_{\text {eight }}$$'Using this short cut, rewrite each binary number as an octal integer. $$111010_{\text {two }}$$

Prove that there exists no integer between 0 and \(1 .\)

The number of lines formed by joining \(n(\geq 2)\) distinct points in a plane, no three of which being collinear, is \(n(n-1) / 2\)

Express the gcd of the given integers as a linear combination of them. $$18,28$$

Using the big-oh notation, estimate the growth of each function. $$f(n)=\sum_{i=1}^{n}\lceil i / 2\rceil$$

The number of diagonals of a convex \(n\) -gon \(^{*}\) is \(n(n-1) / 2 \geq 3\).

Sort the following lists using the bubble sort algorithm. 19,17,13,8,5

The binary representation of an integer can conveniently be used to find its octal representation. Group the bits in threes from right to left and replace each group with the corresponding octal digit. For example, $$243=11110011_{\text {two }}=011 \quad 110 \quad 011_{\text {two }}=363_{\text {eight }}$$'Using this short cut, rewrite each binary number as an octal integer. $$10110101_{\text {two }}$$

Let \(a \in \mathbf{Z} .\) Prove that no integer exists between \(a\) and \(a+1\)

Express the gcd of the given integers as a linear combination of them. $$12,29$$

Verify each. $$2^{n}=\mathrm{O}(n !)$$

Let \(a\) be a positive integer and \(p\) a prime number such that \(p | a^{n} .\) Then \(p | a,\) where \(n \geq 1.\) (Hint: Use Exercise 37 in Section 4.2.)

Use the minmax algorithm in Algorithm 4.14 to answer Exercises. Algorithm iterative minmax \((X, n, min, m a x)\) (* This algorithm returns the minimum and the maximum of a list \(X\) of n elements. *) 0\. Begin (* algorithm *) 1\. If \(n \geq 1\) then 2\. begin (* if *) 3\. \(\min -x_{1}\) 4\. \(\max \leftarrow x_{1}\) 5\. for \(i=2\) to \(n\) do 6\. begin (* for *) 7\. if \(x_{1}<\) m i n then 8\. \(\min \leftarrow x_{1}\) 9\. if \(x_{1}>\) max then 10\. \(\max \leftarrow x_{1}\) 11\. endfor 12\. endif 13\. End (* algorithm *) Using the big-oh notation, estimate the number \(c_{n}\) of comparisons in lines 7 and 9 of the algorithm.

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. \(11101 two\)

Let \(n_{0} \in \mathbf{Z}, S\) be a nonempty subset of the set \(T=\left\\{n \in \mathbf{Z} | n \geq n_{0}\right\\}\) and \(\ell^{*}\) be a least element of the set \(T^{*}=\left\\{n-n_{0}+1 | n \in T\right\\} .\) Prove that \(n_{0}+\ell^{*}-1\) is a least element of \(S\)

Verify each. $$2^{n}=\mathbf{O}(n !)$$

Express the gcd of the given integers as a linear combination of them. $$28,15$$

Verify each. $$\sum_{i=0}^{n-1} 2^{i}=\mathrm{O}\left(2^{n}\right)$$

Prove that \(1+2+\ldots+n=n(n+1) / 2\) by considering the sum in the reverse order." (Do not use induction.)

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. $$110111_{\text {two }}$$

Using the well-ordering principle, prove that 1 is the smallest positive integer. (Hint: Prove by contradiction.)

Prove that \(1+2+\cdots+n=n(n+1) / 2\) by considering the sum in the reverse order." (Do not use induction.)

Two prime numbers that differ by 2 are called twin primes. For example, 5 and 7 are twin primes. Prove that one more than the product of two twin primes is a perfect square. (Twin primes played a key role in 1994 in establishing a flaw in the Pentium chip, manufactured by Intel Corporation.)