Chapter 4

Arrange the hexadecimal numbers \(1076,3056,3 \mathrm{CAB}, 5 \mathrm{ABC},\) and CACB in order of increasing magnitude.

A magic 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 magic 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\).

Let \(p, q,\) and \(r\) be prime numbers, and \(i, j,\) and \(k\) whole numbers. Find the sum of the positive divisors of each. $$p^{i}$$

What can you say about the ones bit in the binary representation of an even integer? An odd integer?

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. If \(a | b\) and \(a | c,\) then \(a |(b-c)\)

Let \(p, q,\) and \(r\) be prime numbers, and \(i, j,\) and \(k\) whole numbers. Find the sum of the positive divisors of each. $$p^{i} q^{j}$$

Find the value of the base \(b\) in each case. $$ 54_{b}=64 $$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. If \(a | b,\) then \(a | b c\)

Find the value of the base \(b\) in each case. $$54 b=64$$

Let \(p, q,\) and \(r\) be prime numbers, and \(i, j,\) and \(k\) whole numbers. Find the sum of the positive divisors of each. $$p^{i} q^{j} r^{k}$$

Find the value of the base \(b\) in each case. $$1001_{b}=9$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. Let \(r\) be the remainder when \(a\) is divided by \(b .\) Let \(d=\operatorname{gcd}\\{a, b\\}\) and \(d^{\prime}=\operatorname{gcd}\\{b, r\\} .\) Then \(d^{\prime} | d\).

Let \(p\) be a prime and \(n \in \mathbb{N} .\) Prove that \(p^{n}\) is not a perfect number. (Hint: Prove by contradiction.)

Find the value of the base \(b\) in each case. $$1001_{b}=126$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. Let \(a > b .\) Then \(\operatorname{gcd}\\{a, b\\}=\operatorname{gcd}\\{a, a-b\\}\).

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

Find the number of times the statement \(x \leftarrow x+1\) is executed by each loop. $$ \begin{array}{c}{\text { for } 1=1 \text { to } n \text { do }} \\ {\text { for } j=1 \text { to } 1 \text { do }} \\ {x \leftarrow x+1}\end{array} $$

Find the value of the base \(b\) in each case. $$144_{b}=49$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. Let \(a > b .\) Then \(\operatorname{gcd}\\{a, b\\}=\operatorname{gcd}\\{b, a+b\\}\).

Find the number of times the statement \(x \leftarrow x+1\) is executed by each loop. for \(i=1\) to \(\mathrm{n}\) do for \(j=1\) to \(i\) do for \(k=1\) to \(i\) do \(x \leftarrow x+1\)

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. The gcd of \(a\) and \(b\) is unique. (Hint: Assume two ged's \(d\) and \(d^{\prime} ;\) show that \(d=d^{\prime} .\) )

Use the insertion sort algorithm in Algorithm 4.12 to answer Exercises \(37-39 .\) Use the insertion sort algorithm in Algorithm 4.12 to answer Exercises \(37-39 .\) Algorithm insertion sort \((x, n)\) (* This algorithm sorts a list \(x\) of n elements into ascending order by inserting a new element in the proper place at the end of each pass.") 0\. Begin (* algorithm ") 1\. for \(1=2\) to \(n\) do 2\. begin \((* \text { for } *)\) 3\. temp \(\leftarrow x_{i}\)(" temp is a temporary variable ") 4\. \(j=1-1\) 5\. while \(j \geq 1\) do 6\. begin (" while ") 7\. if \(x_{j}>\) temp then 8\. \(x_{1+1} \leftarrow x_{j}\) 9\. \(1+j-1\) 10\. endwhile 11\. \(x_{j+1}+\) temp 12\. endfor 13\. End (" algorithm *) Sort each list. \(3,13,8,6,5,2\)

Find the number of times the statement \(x \leftarrow x+1\) is executed by each loop. $$ \begin{array}{c}{\text { for } i=1 \text { to } n \text { do }} \\ {\text { for } j=1 \text { to } 1 \text { do }} \\ {\text { for } k=1 \text { to } j \text { do }} \\ {x \leftarrow x+1}\end{array} $$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. If \(p | a b,\) then \(p | a\) or \(p | b\) [Hint: Assume \(p | a b\) and \(p y a .\) since \(p / a, \operatorname{gcd}\\{p, a\\}=1.]\)

Verify each. $$4 n^{2}+2 n-3=\Omega\left(n^{2}\right)$$

Find the number of times the statement \(x \leftarrow x+1\) is executed by each loop. $$ \begin{array}{c}{\text { for } i=1 \text { to } n \text { do }} \\ {\text { for } j=1 \text { to } 1 \text { do }} \\ {\text { for } k=1 \text { to } 1 \text { do }} \\ {\text { for } 1=1 \text { to } 1 \text { do }} \\\ {x-x+1}\end{array} $$

Use the insertion sort algorithm in Algorithm 4.12 to answer Exercises Algorithm insertion sort \((x, n)\) (* This algorithm sorts a list \(x\) of n elements into ascending order by inserting a new element in the proper place at the end of each pass. \(^{\star}\) ) 0\. Begin \(\left(^{\star} \text { al gori thm }^{\star}\) ) \right. 1\. for \(i=2\) to \(n\) do 2\. begin (* for *) 3 \(\operatorname{temp} \leftarrow x_{i}\) \(\left(* \text { temp is a temporary variable }^{\star}\right)\) \(4 . \quad j \leftarrow i-1\) 5\. while \(j \geq 1\) do

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. Any two consecutive integers are relatively prime.

Verify each. $$2 n^{3}-3 n^{2}+4 n=\Omega\left(n^{3}\right)$$

Use the insertion sort algorithm in Algorithm 4.12 to answer Exercises Algorithm insertion sort \((x, n)\) (* This algori thm sorts a list \(x\) of \(n\) elements into ascending order by inserting a new element in the proper place at the end of each pass. \(^{\star}\) ) \(0 .\) Begin \(\left(^{\star} \text { al gori thm }^{\star}\right)\) 1\. for \(i=2\) to \(n\) do 2\. begin (* for *) 3\. \(\quad \operatorname{temp} \leftarrow x_{i}\) \(\left(^{\star} \text { temp is a temporary variable }^{\star}\right)\) \(4 . \quad j \leftarrow i-1\) 5\. while \(j \geq 1\) do

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. Let \(d=\operatorname{gcd}\\{a, b\\} .\) Then \(a / d\) and \(b / d\) are relatively prime.

Verify each. $$3+\lg n=\Omega(\lg n)$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. \(\operatorname{gcd}\\{n a, n b\\}=n \cdot \operatorname{gcd}\\{a, b\\}\)

Verify each. $$3 \lg n+2=\Omega(\lg n)$$

Let \(a_{n}\) denote the number of times the statement \(x \leftarrow x+1\) is executed in the following loop: for \(i=1\) to \(n\) do for \(j=1\) to \(\lfloor i / 2\rfloor d o\) \(x \leftarrow x+1\) Show that $$a_{n}=\left\\{\begin{array}{ll} \frac{n^{2}}{4} & \text { if } n \text { is even } \\ \frac{n^{2}-1}{4} & \text { if } n \text { is odd } \end{array}\right.$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. \(\operatorname{gcd}\\{\operatorname{gcd}\\{a, b\\}, c\\}=\operatorname{gcd}\\{a, \operatorname{gcd}\\{b, c\\}\\}\)

Find the number of trailing zeros in the decimal value of each. $$100 !$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. Let \(a | c\) and \(b | c,\) where \(a\) and \(b\) are relatively prime numbers. Then \(a b | c\).

Find the number of trailing zeros in the decimal value of each. $$378 !$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. 2 and 3 are the only two consecutive integers that are primes.

Find the number of trailing zeros in the decimal value of each. $$500 !$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. \(3,5,\) and 7 are the only three consecutive odd integers that are primes.

Let \(f_{1}(n)=O(g(n))\) and \(f_{2}(n)=k f_{1}(n),\) where \(k\) is a positive constant. Show that \(f_{2}(n)=O(g(n))\)

Let \(f_{1}(n)=\mathrm{O}(g(n))\) and \(f_{2}(n)=k f_{1}(n),\) where \(k\) is a positive constant. Show that \(f_{2}(n)=\mathrm{O}(g(n))\).

Find the number of trailing zeros in the decimal value of each. $$1000 !$$

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. If \(p\) and \(p^{2}+8\) are primes, then \(p^{3}+4\) is also a prime. (D. L. Silverman, 1968)

Consider the constant function \(f(n)=k .\) Show that \(f(n)=\mathrm{O}(1)\).

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. If \(p\) and \(p+2\) are twin primes, then \(p\) must be odd.

Let \(f(n)=O(h(n))\) and \(g(n)=O(h(n))\) . Verify each. $$\left(f^{\prime}+g\right)(n)=O(h(n))$$

Prove each, where \(t_{n}\) denotes the \(n\) th triangular number and \(n \geq 2\). $$8 t_{n-1}+4 n=(2 n)^{2}$$