Chapter 1

How many quantifiers (and what sorts) are in the following sentence? "Everybody has some friend that thinks they know everything about a sport."

An integer \(n\) is doubly-even if it is even, and the integer \(m\) guaranteed to exist because \(n\) is even is itself even. Is 0 doubly-even? What are the first 3 positive, doubly-even integers?

Find the prime factorizations of the following integers. (a) 105 (b) 414 (c) 168 (d) 1612 (e) 9177

The domain of a function (or binary relation) is the set of numbers appearing in the first coordinate. The range of a function (or binary relation) is the set of numbers appearing in the second coordinate. Consider the set \\{0,1,2,3,4,5,6\\} and the function \(f(x)=x^{2}(\bmod 7)\) Express this function as a relation by explicitly writing out the set of ordered pairs it contains. What is the range of this function?

Use the sieve of Eratosthenes to find all prime numbers up to 100 . $$ \begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\ 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\ 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\ 51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\ 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 \\ 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90 \\ 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 \end{array} $$

What relation on the numbers from 1 to 10 does the following set of ordered pairs represent? $$ \begin{array}{c} \\{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10) \\ (2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(2,10) \\ (3,3),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(3,10), \\ (4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(4,10), \\ (5,5),(5,6),(5,7),(5,8),(5,9),(5,10), \\ (6,6),(6,7),(6,8),(6,9),(6,10), \\ (7,7),(7,8),(7,9),(7,10), \\ (8,8),(8,9),(8,10), \\ (9,9),(9,10), \\ (10,10)\\} \end{array} $$

If a number \(x\) is even, it's easy to show that its square \(x^{2}\) is even. The lemma that went unproved in this section asks us to start with a square \(\left(x^{2}\right)\) that is even and deduce that the UN-squared number \((x)\) is even. Perform some numerical experimentation to check whether this assertion is reasonable. Can you give an argument that would prove it?

The octal representation of an integer uses powers of 8 in place notation. The digits of an octal number run from 0 to 7 , one never sees 8 's or 9 's. How would you represent 8 and 9 as octal numbers? What octal number comes immediately after \(777_{8}\) ? What (decimal) number is \(777_{8}\) ?

What would be the largest prime one would sieve with in order to find all primes up to \(400 ?\)

Identify each as rational or irrational. (a) \(5021.2121212121 \ldots\) (b) \(0.2340000000 \ldots\) (c) \(12.31331133311133331111 \ldots\) (d) \(\pi\) (e) \(2.987654321987654321987654321 \ldots\)

One method of converting from decimal to some other base is called repeated division. One divides the number by the base and records the remainder \(-\) one then divides the quotient obtained by the base and records the remainder. Continue dividing the successive quotients by the base until the quotient is smaller than the base. Convert 3267 to base- 7 using repeated division. Check your answer by using the meaning of base- 7 place notation. (For example \(54321_{7}\) means \(5 \cdot 7^{4}+\) \(\left.4 \cdot 7^{3}+3 \cdot 7^{2}+2 \cdot 7^{1}+1 \cdot 7^{0} .\right)\)

Trace through the Euclidean algorithm with inputs \(a=3731\) and \(b=2730,\) each time the assignment statement that calls the division algorithm is encountered write out the expression \(a=q b+r\).

Write your own sentences containing four quantifiers. One sentence in which the quantifiers appear \((\forall \exists \forall \exists)\) and another in which they appear \((\exists \forall \exists \forall) .\)

The "see and say" sequence is produced by first writing a \(1,\) then it- erating the following procedure: look at the previous entry and say how many entries there are of each integer and write down what you just said. The first several terms of the "see and say" sequence are \(1,11,21,1112,3112,211213,312213,212223, \ldots . .\) Comment on the ra- tionality (or irrationality) of the number whose decimal digits are ob- tained by concatenating the "see and say" sequence. $$ 0.1112111123112211213 \ldots $$

Write a proof that \(\sqrt{3}\) is irrational.

Complete the following table which is related to Conjecture 1 . \begin{tabular}{c|c|c|c} $$ \begin{array}{r|c|c|c} p & 2^{p}-1 & \text { prime? } & \text { factors } \\ \hline 2 & 3 & \text { yes } & 1 \text { and } 3 \\ 3 & 7 & \text { yes } & 1 \text { and } 7 \\ 5 & 31 & \text { yes } & \\ 7 & 127 & & \\ 11 & & & \end{array} $$

Give a description of the set of rational numbers whose decimal expansions terminate. (Alternatively, you may think of their decimal expansions ending in an infinitely-long string of zeros.)

A function \(f(x)\) is said to be invertible if there is another function \(g(x)\) such that \(g(f(x))=x\) for all values of \(x\). (Usually, the inverse function, \(g(x)\) would be denoted \(\left.f^{-1}(x) .\right)\) Suppose a function is presented to you as a relation - that is, you are just given a set of pairs. How can you distinguish whether the function represented by this list of input/output pairs is invertible? How can you produce the inverse (as a set of ordered pairs)?

Find the first 20 decimal places of \(\pi, 3 / 7, \sqrt{2}, 2 / 5,16 / 17, \sqrt{3}, 1 / 2\) and \(42 / 100 .\) Classify each of these quantity's decimal expansion as: terminating, having a repeating pattern, or showing no discernible pattern.

Consider the process of long division. Does this algorithm give any in- sight as to why rational numbers have terminating or repeating decimal expansions? Explain.

Give an argument as to why the product of two rational numbers is again a rational.

Try the following conversions between various number systems: (a) Convert 30 (base 10 ) to binary. (b) Convert 69 (base 10 ) to base 5 . (c) Convert \(1222_{3}\) to binary. (d) Convert \(1234_{7}\) to base 10 . (e) Convert \(E E E D_{15}\) to base 12. (Use \(\\{1,2,3 \ldots 9, d, e\\}\) as the digits in base \(12 .)\) (f) Convert \(678_{9}\) to hexadecimal.

A famous conjecture that is thought to be true (but for which no proof is known) is the Twin Prime conjecture. A pair of primes is said to be twin if they differ by 2. For example, 11 and 13 are twin primes, as are 431 and \(433 .\) The Twin Prime conjecture states that there are an infinite number of such twins. Try to come up with an argument as to why 3,5 and 7 are the only prime triplets.

Perform the following computations with complex numbers (a) \((4+3 i)-(3+2 i)\) (b) \((1+i)+(1-i)\) (c) \((1+i) \cdot(1-i)\) (d) \((2-3 i) \cdot(3-2 i)\)

It is a well known fact that if a number is divisible by 3 , then 3 divides the sum of the (decimal) digits of that number. Is this result true in base \(7 ?\) Do you think this result is true in any base?

Another famous conjecture, also thought to be true \(-\) but as yet unproved, is Goldbach's conjecture. Goldbach's conjecture states that every even number greater than 4 is the sum of two odd primes. There is a function \(g(n),\) known as the Goldbach function, defined on the positive integers, that gives the number of different ways to write a given number as the sum of two odd primes. For example \(g(10)=2\) since \(10=5+5=7+3\). Thus another version of Goldbach's conjecture is that \(g(n)\) is positive whenever \(n\) is an even number greater than \(4 .\) Graph \(g(n)\) for \(6 \leq n \leq 20\)

The conjugate of a complex number is denoted with a superscript star, and is formed by negating the imaginary part. Thus if \(z=3+4 i\) then the conjugate of \(z\) is \(z^{*}=3-4 i\). Give an argument as to why the product of a complex number and its conjugate is a real quantity. (I.e. the imaginary part of \(z \cdot z^{*}\) is necessarily \(0,\) no matter what complex number is used for \(z\).)

Suppose that 340 pounds of sand must be placed into bags having a 50 pound capacity. Write an expression using either floor or ceiling notation for the number of bags required.

True or false? $$ \left\lfloor\frac{n}{d}\right\rfloor<\left\lceil\frac{n}{d}\right\rceil $$ for all integers \(n\) and \(d>0\). Support your claim.

What is the value of \(\lceil\pi\rceil^{2}-\left\lceil\pi^{2}\right\rceil ?\)