Description
Problem 1 (21 points)
One way to test whether an integer n is prime is to check if n is divisible by any positive integer i
where i = 2, i = 3, . . . , i = b
√
nc. (Note: The ‘floor’ of a number x, denoted bxc, is the greatest
integer that is at most x). If no such i divides n, then n must be prime, otherwise it is not prime;
you will prove this fact as part of the following.
(a) (10+1 points) Prove the last statement above; that is, prove that any positive integer n that
is not prime has a factor (other than 1) less than or equal to √
n.
(b) (10 points) Implement the procedure above as the function isPrime(x) in hw1.py. The
input to the function is a positive integer x, and the output is TRUE if x is prime, and FALSE
otherwise.
Problem 2 (32 points)
Let n be a positive integer with k digits. Consider the following procedure. “Split” n into two
numbers by taking the leftmost k − 1 digits and the rightmost digit, subtract twice the latter from
the former, and take the absolute value of that difference. For example, performing this procedure
on 1234 yields 115. It turns out that the number obtained by this procedure is divisible by 7 if and
only if the original number is divisible by 7; you will prove this fact as part of the following.
(a) (10+1 points) Prove that the prove a number n is divisible by 7 if and only if the result
from performing the procedure above on n is divisible by 7.
(b) (10+1 points) The previous part implies that procedure above can be repeatedly successively, always maintaining that the resulting number is divisible by 7 if and only if the original
number is as well. Show that for any positive integer x with at least two digits, repeating the
procedure above will eventually result in a number with one digit. For example, starting with
1234, applying the procedure twice yields 1.
[Hint: Show that for any positive integer x with at least two digits, the number obtained by
the procedure above always results in a number strictly less than x.]
(c) (10 points) Using the two facts above, implement the procedure above as a recursive
function isDivBySeven(x) in hw1.py as follows. For any input non-negative integer x,
isDivBySeven(x) writes x to STDOUT (which is already implemented for you), and
then:
1. If x is a single digit (less than 10), TRUE (the Boolean type) is returned if x is divisible
by 7, and FALSE is returned otherwise.
2. Otherwise, the procedure above is applied to x to obtain a new number y, and then
isDivBySeven(y) is returned.
For example, by calling isDivBySeven(1234), the numbers 1234, 115, and 1 will be
printed to the console (each number on its own line), then FALSE will be returned.
Problem 3 (10+1 points)
Suppose a, b, and n are positive integers such that b > a. Prove the following:
If b − a is even then a
n + b
n
is even.