COGS 501 Quiz

[1pt] Prove that the product of an even integer with an odd integer is even.

Let \(m\) be an even integer and \(n\) be an odd integer. By definition of even numbers, there exists an integer \(k\) such that \(m = 2k\). By definition of odd numbers, there exists an integer \(j\) such that \(n = 2j + 1\). Then \(mn = (2k)(2j + 1) = 4kj + 2k = 2(2kj + k)\). Since \(2kj + k\) is an integer, we conclude that \(mn\) is even.
[2pts] Prove that if \(a\) and \(b\) are nonzero integers, \(a\mid b\) and \(a+b\) is odd, then \(a\) is odd.

Since \(a \mid b\), there exists an integer \(k\) such that \(b = ak\). Therefore, \(a + b = a + ak = a(1 + k)\). Since \(a + b\) is odd, and \(1 + k\) is an integer, it follows that \(a\) must be odd. If \(a\) were even, then the product \(a(1 + k)\) would be even, contradicting the assumption that \(a + b\) is odd. Hence, \(a\) is odd.
[2pts] Define the mod function using proc_seq. You are not allowed to touch % or // operators. Those who get the correct result for negatives will receive [2pts] bonus credit.

If you do not care about negatives, the solution is straightforward:
```
def mod(a, b):
   """Compute a mod b for a>=0."""
   while a >= b:
       a = a - b
   return a
```
As the solution for the positive case requires only a single iteration variable, pro_seq would be overkill, but here is how to do it with proc_seq for the record:
```
def mod(a, b):
   """Compute a mod b for a>=0."""
   return proc_seq(a,
                   seq=lambda x: x - b,
                   alive=lambda x: x>=0,
                   update =lambda store, x : x,  
                   init = 0)
```
Now, how to get the bonus. A practical strategy doable in the quiz setting is to divide the problem into two cases: when a is non-negative, and when a is negative. For the negative case, we can repeatedly add b to a until it becomes non-negative. We already know what to do for the non-negative case. Here is the code:
```
def mod(a,b):
    """Compute a mod b."""
    if a >= 0:
        while a >= b:
            a = a - b
        return a
    else:
        while a < 0:
            a = a + b
        return a
```
Can we write a more general code that handles both negative and non-negatives in a unified way? Yes, we can, if we understand what really is meant by division. The common-sense conception of division takes the quotient to be the answer to the question “how many bs are there in a?”, and remainder to be “what is left behind when we remove those bs from a”. The mathematical concept of quotient, on the other hand, is “what is the largest integer \(q\) smaller than \(a\) such that \(b=kq\) for some integer \(k\)?” The remainder in this conception is \(r = a - bq\). In dividing -7 by 3, we find the largest integer smaller than -7 that is divisible by 3. The answer -9 is \(kq\) and the remainder is \(-7 - (-9) = 2\).

With this understanding, we can write a function that works for both negative and non-negative \(a\)s. First, we need a boolean function that decides whether a given number \(a\) divides \(b\) (i.e., \(a \mid b\)). We can do this without caring about the sign of \(a\) and \(b\), because the concept of divisibility without a remainder is independent of sign. Here is the code:
```
def divides(a,b):
    """Return True if a divides b (a != 0).

    >>> divides(3,9)
    True
    >>> divides(2,9)
    False
    >>> divides(9,2)
    False
    >>> divides(5,0)
    True
    """
    a,b = abs(a), abs(b)
    while b >= a:
        b = b - a
    return  b == 0
```
With divides at our disposal, now we can see that \(a \bmod b\) can be computed by counting down from \(a\) starting with 0 and in steps of 1 until we find an integer that \(b\) divides. The remainder will simply be the count. This strategy of counting down in steps of 1 applies uniformly for negatives and non-negatives. (We are so used to count in steps of \(b\) when asked \(a\bmod b\), isn’t it interesting that you also need to count in steps of 1?) Now proc_seq can be invited on to the stage for the final touch:
```
def mod(a,b):
    """Compute a mod b.

    >>> mod(10, 3)
    1
    >>> mod(9, 9)
    0
    >>> mod(3, 10)
    3
    >>> mod(-7,3)
    2
    """
    return proc_seq(a,
                    seq=lambda x: x -1,
                    alive=lambda x: not divides(b,x),
                    update=lambda store, x : store +1,
                    init=0)
```