Important information: In most of the upcoming problems you will be asked to write functions with their names being indicated in the problem. It is very important to use exactly the names provided (for example, myfunction()) as you will be able to reuse your functions in future exercises and also because our in-class tests are automatically graded. If you do not use the exact name as required (for example using myFunction()) your function will not be executable and you will lose marks. Also, when asked to write functions, make it a habit to write a function main() where all the testing is done. This main() function should define meaningful input parameters, call the functions, and output the result for testing.
Here is a simple example where we have been asked to write functions myfunction1() and myfunction2() and we are testing both of them using a main() function:</font>
def myfunction1(a, b):
"""
Takes two input arguments a and b and returns their sum.
"""
s = a + b
return s
def myfunction2(a, b):
"""
Takes two input arguments a and b and returns their product.
"""
s = a * b
return s
def main():
a = 5
b = 3
print(myfunction1(a, b)) # hopefully outputs 8
print(myfunction2(a, b)) # hopefully outputs 15
main()
Problem 1. Write a function max_digit(n, d, r) that works like digit_sum from the lectures but, instead of returning the sum of the digits of n, returns the maximum digit of n that gives the reminder r when divided by d. Assign the appropriate default values for any of the parameters for which it makes sense to do so.
Notice that this maximum is undefined for some numbers. Situations like this are usually handled with exceptions, which will be covered later in this course. For now, detect the problematic case(s) and return an invalid value -1.
Write a main() function that tests this function, i.e., assigns some values to variables n, d, and r, and then prints the maximum digit of n that gives the reminder r when divided by d.
Problem 2. Write a function binom(n, k) that returns the binomial coefficient
$$\binom{n}{k} := \frac{n!}{k!(n-k)!}$$
for given natural numbers n and k. Return zero when $n < 0$ or $k < 0$.
Be careful to compute and return an integer (not a floating point number).
Also, write binomf(n, k) which does the same thing using floating point arithmetic (but otherwise exactly the same algorithm).
Write a main() function that assigns some values to n and k, calls binom(n, k) and binomf(n, k) and prints their values, and the difference of these values. Test what happens for fairly large inputs (for example, (n, k) = (100, 50)).
If you want to make a more general function that will work correctly for all real values of $n$, you can check your results at Wolfram|Alpha, for example like this.
Problem 3. Write a function prime(n) that returns True if n is a prime number and False otherwise. You may use the definition as a criterion:
A number $n$ is prime if it is a natural number with exactly two distinct divisors.
Equivalently, $n$ is prime if $n > 1$ and is not divisible by any integer strictly between 1 andn.
Write a main() function that loads integers until it gets a negative number or a zero. Using the function prime(n), the main() function should print the product of all the loaded prime numbers. If no primes were loaded, the function should instead print an appropriate descriptive message.
Problem 4. We say that a number $n$ is rich if its absolute value is smaller than the sum of all its divisors except itself. For example, $12 < 1+2+3+4+6 = 16$ is considered rich, while $16 > 1+2+4+8 = 15$ is not.
Write a function rich(n) that returns True if n is rich and False otherwise.
Further, write a main() function that assigns a number $k \in \mathbb{N}$ and prints all the rich numbers between $1$ and $k$ (inclusive).
For example, the rich numbers smaller than $50$ are: $12, 18, 20, 24, 30, 36, 40, 42, 48$.
The next two problems go beyond the scope of the course. However, they may be useful, especially for students interested in combinatorics.
These two will not be part of any exams!
Problem 5. $\color{red}{\star}$ Write a function f that takes an integer parameter x and returns the value
$$f(x) = \begin{cases}
f(17 - |x|), & x < 2, \\
f(d), & \text{$x$ is a composite number and $d$ is its largest divisor such that $d < x$}, \\
x, & \text{otherwise}.
\end{cases}$$
We say that $x$ is a composite number if $x > 1$ and $x$ is not a prime.
Write a main() function that loads x until it loads x = 0, and then writes the value f(x) for each of the loaded numbers.
Problem 6. $\color{red}{\star}$ Write a function f that takes an integer parameter x and returns the value
$$f(x) = \begin{cases}
x^2, & x < 9, \\
f(g(x)), & \text{$x \ge 9$ is even}, \\
f(h(x+1)), & \text{otherwise},
\end{cases}$$
where $g(x) = \left\lceil \frac{x}{2} \right\rceil$ is the ceiling of $\frac{x}{2}$ and $h(x) = \left\lfloor \frac{x}{2} + 1 \right\rfloor$ is the floor of $\frac{x}{2}+1$.
Write a main() function that loads x until it loads x = 0, and then writes the value f(x) for each of the loaded numbers.
Hints for Problems 5 and 6:
These are simple examples of recursive functions. A function in Python (and most other modern languages) can invoke itself just like it can invoke any other function. However, there are two major things to remember:
x, then there will be two variables x in the memory, each belonging to its own invocation. The two are in no way related (apart from having the same name), and each invocation will see only its own x.Here is a sketch how such a function may look:
def f(x):
if some_condition:
return f(some_expression)
if some other condition:
return f(some_other_expression)
...
return an_expression_that_covers_the_case_when_no_prior_condition_was_met
Write auxiliary functions (the one for finding $d$ in Problem 5, $h$ and $g$ in Problem 6), to make it easier to organize and read your code.