MTH 225(M) Exercise-Set #6

Due March 18 (Wednesday)

In "Discrete Mathematics (...)" by Rosen, read the Appendix, from the bottom of page 142 to page 145, Chapter 3 ("The Fundamentals: Algorithms, the Integers [...]") from the beginning through Section 3.1, and Sections 3.4–3.5 through the middle of page 212.
Please do exercises in teams of two; doing so garners 5% extra credit.
Where appropriate, show intermediate steps/explanations for obtaining answers.

1. [1 homework point] Express 3^-4 as a fraction a/b, with a and b being integers (literals). Try to do this exercise without using a calculator.
2. [1 homework point] What is the value of (-3)⁴ ? Try to do this exercise without using a calculator.
3. [1 homework point] What is the value of 1¹⁰ ? Try to do this exercise without using a calculator.
4. [1 homework point] What is the value of 1000⁰ ? Try to do this exercise without using a calculator.
5. [1 homework point] What is the value of lg(512)? Try to do this exercise without using a calculator.
6. [1 homework point] What is the value of lg(1/128)? Try to do this exercise without using a calculator.
7. [1 homework point] What is the value of lg(2)? Try to do this exercise without using a calculator.
8. [1 homework point] What is the value of lg(2¹⁰⁰⁰)? Try to do this exercise without using a calculator.
Rem. "lg(z)" means "log₂(z)".
[5 homework points] Give the complete, thorough prime factorizations of each of the following numbers: 1980, 2009, 2010, 2011, 2012. Your final answers for this exercise should appear like the following:
- 2000 := 2⁴ * 5³
- 2001 := 3 * 23 * 29
- 2002 := 2 * 7 * 11 * 13
- 2003 is prime considering that it's not evenly divisible by 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, or 43 and the squares of further primes (47 etc.) are larger than 2003.
- 2004 := 2² * 3 * 167
  167 is prime considering that it's not evenly divisible by 2, 3, 5, 7, or 11 and the squares of further primes (13 etc.) are larger than 167.
You can do the factoring however you want; you do not need to use the algorithm(s) for factorization specified in our textbook. Rem. the primes less than 100 are listed near the bottom of page 210 of our textbook.
Try to do this exercise without using a calculator.
Show intermediate steps/explanations for obtaining answers.
[3 homework points] Show that for every value of n, 5ⁿ + 4*5ⁿ =?= 5⁽ⁿ⁺¹⁾ is true, regardless of what n's value may be.
Incidentally, note that substituting a few values for n such as 2 and/or 3 and/or 5 would show only that the equation is true for the specific values that you test; it wouldn't show that the equation is true for other values of n which you haven't tested. What you need to do here is apply algebra to the left-hand side of that equation, "5ⁿ + 4*5ⁿ"; collect terms, etc....
Show intermediate steps/explanations for obtaining answers.
[4 homework points] Using algebra, show that the following is true, regardless of what value may be used for a:
```
    (a-1)*2^{^(a+1)} + 2  +  [a+1]*2^{^[a+1]} =?=  ([a+1]-1)*2^{^([a+1]+1)} + 2
```
Incidentally, note that substituting a few values for a such as 2 and/or 3 and/or 5 would show only that the equation is true for the specific values that you test; it wouldn't show that the equation is true for other values of a which you haven't tested. What you need to do here is apply algebra to the terms in that equation: maybe multiply things out, collect terms, etc....
Show intermediate steps/explanations for obtaining answers.
[8 homework points]
1. Express 0.0375 as a fraction a/b in lowest terms, with a and b being integers (literals).
  Suggestion: One way to do this is to use your knowledge of what decimal floating-point representation means. For example, "0.6" means "6/10", which reduces to lowest terms 3/5.
  Try to do this without using a calculator.
2. Give the complete prime factorizations of 30 and 6561, and also of the values a and b that you determine in Part 1 (above).
  Try to do this without using a calculator.
3. Express lg(30), lg(6561), and lg(0.0375) as simplified sums/differences of integers and multiples of lg(3) and lg(5). (Rem. "lg(z)" means "log₂(z)".)
  For examples:
  • lg(250) == lg(2*5³) == lg(2) + lg(5³) == 1 + 3*lg(5)
  • lg(0.6) == lg(3/5) == lg(3) - lg(5)
  Try to do this without using a calculator.
Show intermediate steps/explanations for obtaining answers.

Acknowledgement: Some of these exercises are derived from Richard Johnsonbaugh.
[2 homework points] Give the prime factorization of 11! (note the "!").
Try to do this without using a calculator.
Suggestion (to facilitate doing the work without using a calculator): don't calculate the value of 11! — don't do any multiplication at all; write out 11! as 11*10*9*···*3*2*1 and then work on obtaining prime factors from there....
Show intermediate steps/explanations for obtaining answers.
[3 homework points] Use algebra, including properties of factorial ("x!"), to reduce the following expression to an equivalent one that is as simple as possible:
```
      n!
    ------*(n+1)*(k+1)
    (k+1)!
```
Show intermediate steps/explanations for obtaining answers.
[3 homework points]
1. Exhibit a pair of decimal floating-point numbers x and y for which ⌈x + y⌉ ≠ ⌈x⌉ + ⌈y⌉, i.e. |¯x + y¯| != |¯x¯| + |¯y¯|.
  Show all the intermediate values: x + y, ⌈x + y⌉, ⌈x⌉, ⌈y⌉, and ⌈x⌉ + ⌈y⌉.
2. Exhibit a pair of decimal floating-point numbers x and y for which ⌊x + y⌋ ≠ ⌊x⌋ + ⌈y⌉, i.e. |_x + y_| != |_x_| + |¯y¯|.
  Show all the intermediate values: x + y, ⌊x + y⌋, ⌊x⌋, ⌈y⌉, and ⌊x⌋ + ⌈y⌉.
[4 homework points] Calculate the value of the expression ⌈L/2⌉ + ⌈L/2⌉ - 1 for each of the following values for L: 0, 1, 2, 3, 4, 5.
In your intermediate work here, include showing the decimal values of L/2.
Try to do this without using a calculator.
You should see that it appears that in each case, no matter what the value of L is, ⌈L/2⌉ + ⌈L/2⌉ - 1 ≤ L. Write an English explanation of why this appears to always be true for every nonnegative integer value for L.
This condition "⌈L/2⌉ + ⌈L/2⌉ - 1 ≤ L" arises in connection with B⁺-trees, which are data structures with good properties of efficient access — databases use them.
[5 homework points] For each of following values of n and d, find the integer quotient q := ⌊n/d⌋ and the integer remainder r := n - d*q:
(In case your Web-browser isn't rendering characters properly, here's alternative notation for the integer quotient: q := |_n/d_|.)
1. n := 53, d := 6
2. n := -53, d := 6
3. n := 3, d := 6
4. n := 0, d := 6
5. n := 6, d := 6
6. n := 53, d := 53
Try to do this without using a calculator.
[4 homework points] The months with Friday the 13th in year y are found in row #f13(y) in the table below, where f13(y) is calculated from y as follows:
f13(y) := ( y + ⌊(y-1)/4⌋ - ⌊(y-1)/100⌋ + &lfloor(y-1)/400⌋ ) mod 7
i.e. f13(y) := ( y + |_(y-1)/4_| - |_(y-1)/100_| + |_(y-1)/400_| ) mod 7
Here's the table:
```
    f13(y)  if y is not a leap year     if y is a leap year
    ------  -----------------------     -------------------
       0    January, October            January, April, July
       1    April, July                 September, December
       2    September, December         June
       3    June                        March, November
       4    February, March, November   February, August
       5    August                      May
       6    May                         October
```
For example for next year, 2010:
f13(2010) := ( 2010 + ⌊(2010-1)/4⌋ - ⌊(2010-1)/100⌋ + &lfloor(2010-1)/400⌋ ) mod 7
:= ( 2010 + 502 - 20 + 5 ) mod 7
:= 2497 mod 7
:= 5,
and 2010 is not a leap year; so looking at the appropriate entry in the table above, in the year 2010 (only) the month of August will have a Friday the 13th.
Determine the months with Friday the 13th in 2001, in 2004, and in our current year right now.
Try to do this without using a calculator.
Show intermediate steps/explanations for obtaining answers.
1. [4 homework points] Perform the following integer divisions a/d, obtaining in each case an integer quotient q and a remainder r: 6!/4!, 5!/2!, 3!/1!, 7!/6!, 4!/0!, 8!/5!, 9!/7! .
  Try to do this without using a calculator.
  Suggestion (to facilitate doing the work without using a calculator): write out each of these expressions n!/k! as follows:
  n*(n-1)*(n-2)*···*3*2*1
  k*(k-1)*(k-2)*···*3*2*1
  and then cancel common factors (that appear in both the numerator and the denominator) — before really multiplying any numbers together and finally dividing.
  Definitely report the remainders, even if they seem trivial (in the past some students neglected to report them).
2. [2 homework points] You should see that it appears that in each case, no matter what the values of n and k are, as long as 0 ≤ k ≤ n, then k! evenly divides n! .
  Write an explanation of why it should always be true that k! evenly divides n! for any values of n and k — as long as 0 ≤ k ≤ n.