Solutions: You can find the file with solutions for all questions here.

## Questions

### Question 1: Fibonacci

The Fibonacci sequence is a famous sequence in mathematics. The first element in the sequence is 0 and the second element is 1. The nth element is defined as Fn = Fn-1 + Fn-2.

Implement the `fib` function, which takes an integer `n` and returns the `n`th Fibonacci number. Use a `while` loop in your solution.

``````def fib(n):
"""Returns the nth Fibonacci number.

>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
>>> fib(6)
8
>>> fib(100)
354224848179261915075
"""
curr, next = 0, 1
while n > 0:
curr, next = next, curr + next
n -= 1
return curr``````

Use OK to test your code:

``python3 ok -q fib``

### Question 2: Mul_by_num

Using higher order functions, complete the `mul_by_num` function. This function should take an argument and return a one argument function that multiplies any value passed to it by the original number.

``````def mul_by_num(factor):
"""
Returns a function that takes one argument and returns num
times that argument.
>>> x = mul_by_num(5)
>>> y = mul_by_num(2)
>>> x(3)
15
>>> y(-4)
-8
"""
def f(x):
return factor*x
return f``````

Use OK to test your code:

``python3 ok -q mul_by_num``

### Question 3: This Question is so Derivative

Define a function `make_derivative` that returns a function: the derivative of a function `f`. Assuming that `f` is a single-variable mathematical function, its derivative will also be a single-variable function. When called with a number `a`, the derivative will estimate the slope of `f` at point `(a, f(a))`.

Recall that the formula for finding the derivative of `f` at point `a` is:

where `h` approaches 0. We will approximate the derivative by choosing a very small value for `h`. The closer `h` is to 0, the better the estimate of the derivative will be.

``````def make_derivative(f):
"""Returns a function that approximates the derivative of f.

Recall that f'(a) = (f(a + h) - f(a)) / h as h approaches 0. We will
approximate the derivative by choosing a very small value for h.

>>> def square(x):
...     # equivalent to: square = lambda x: x*x
...     return x*x
>>> derivative = make_derivative(square)
>>> result = derivative(3)
>>> round(result, 3) # approximately 2*3
6.0
"""
h=0.00001
def derivative(x):
return (f(x + h) - f(x)) / h
return derivative``````

Use OK to test your code:

``python3 ok -q make_derivative``

### Question 4: Count van Count

Consider the following implementations of `count_factors` and `count_primes`:

``````def count_factors(n):
"""Return the number of positive factors that n has."""
i, count = 1, 0
while i <= n:
if n % i == 0:
count += 1
i += 1
return count

def count_primes(n):
"""Return the number of prime numbers up to and including n."""
i, count = 1, 0
while i <= n:
if is_prime(i):
count += 1
i += 1
return count

def is_prime(n):
return count_factors(n) == 2 # only factors are 1 and n``````

The implementations look quite similar! Generalize this logic by writing a function `count_cond`, which takes in a two-argument predicate function ```mystery_function(n, i)```. `count_cond` returns a count of all the numbers from 1 to `n` that satisfy `condition`.

Note: A predicate function is a function that returns a boolean (`True` or `False`).

``````def count_cond(mystery_function, n):
"""
>>> def divisible(n, i):
...     return n % i == 0
>>> count_cond(divisible, 2) # 1, 2
2
>>> count_cond(divisible, 4) # 1, 2, 4
3
>>> count_cond(divisible, 12) # 1, 2, 3, 4, 6, 12
6

>>> def is_prime(n, i):
...     return count_cond(divisible, i) == 2
>>> count_cond(is_prime, 2) # 2
1
>>> count_cond(is_prime, 3) # 2, 3
2
>>> count_cond(is_prime, 4) # 2, 3
2
>>> count_cond(is_prime, 5) # 2, 3, 5
3
>>> count_cond(is_prime, 20) # 2, 3, 5, 7, 11, 13, 17, 19
8
"""
i, count = 1, 0
while i <= n:
if mystery_function(n, i):
count += 1
i += 1
return count``````

Use OK to test your code:

``python3 ok -q count_cond``

### Question 5: I Heard You Liked Functions...

Define a function `cycle` that takes in three functions `f1`, `f2`, `f3`, as arguments. `cycle` will return another function that should take in an integer argument `n` and return another function. That final function should take in an argument `x` and cycle through applying `f1`, `f2`, and `f3` to `x`, depending on what `n` was. Here's the what the final function should do to `x` for a few values of `n`:

• `n = 0`, return `x`
• `n = 1`, apply `f1` to `x`, or return `f1(x)`
• `n = 2`, apply `f1` to `x` and then `f2` to the result of that, or return `f2(f1(x))`
• `n = 3`, apply `f1` to `x`, `f2` to the result of applying `f1`, and then `f3` to the result of applying `f2`, or `f3(f2(f1(x)))`
• `n = 4`, start the cycle again applying `f1`, then `f2`, then `f3`, then `f1` again, or `f1(f3(f2(f1(x))))`
• And so forth.

Hint: most of the work goes inside the most nested function.

``````def cycle(f1, f2, f3):
""" Returns a function that is itself a higher order function
...     return x + 1
>>> def times2(x):
...     return x * 2
...     return x + 3
>>> identity = my_cycle(0)
>>> identity(5)
5
>>> add_one_then_double = my_cycle(2)
4
>>> do_all_functions = my_cycle(3)
>>> do_all_functions(2)
9
>>> do_more_than_a_cycle = my_cycle(4)
>>> do_more_than_a_cycle(2)
10
>>> do_two_cycles = my_cycle(6)
>>> do_two_cycles(1)
19
"""
def ret_fn(n):
def ret(x):
i = 0
while i < n:
if i % 3 == 0:
x = f1(x)
elif i % 3 == 1:
x = f2(x)
else:
x = f3(x)
i += 1
return x
return ret
return ret_fn``````

Use OK to test your code:

``python3 ok -q cycle``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``