#!/usr/bin/env python
# coding: utf-8

# # Programming with Python
# #### Stefan Güttel, [guettel.com](http://guettel.com)
# 
# ## Exercises: Functions
# 
# 

# ***
# 
# <font color=red>**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](http://en.wikipedia.org/wiki/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](http://www.wolframalpha.com/), for example like [this](http://www.wolframalpha.com/input/?i=binomial%28100%2C50%29).

# **Problem 3.** Write a function `prime(n)` that returns `True` if `n` is a [prime number](http://en.wikipedia.org/wiki/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 and `n`.
# 
# 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$.

# ## Recursive functions
# 
# 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](http://en.wikipedia.org/wiki/Floor_and_ceiling_functions) 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](http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursive_functions_and_algorithms). 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:
#   * As we have mentioned before, the local variables are local to each invocation. So, if a function that invokes itself has a parameter `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`.
#   * There must exist values of the input parameters for which the function does not invoke itself (so called *terminating cases*). Without that, the function will invoke itself indefinitely (or, more precisely, until the program runs out of the available memory).
# 
# * Here is a sketch how such a function may look:
# 
#     ```python3
#     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.