# Homework 2

*Due at 11:59:59 pm on 9/18/2020 .*

## Instructions

Download hw02.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

**Submission:** When you are done, submit with `python3 ok --submit`

. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

**Readings:** This homework relies on following references:

To submit: run `ok`

with the `--submit`

option:

`python3 ok --submit`

## 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 *n*th
element is defined as *F _{n} = F_{n-1} +
F_{n-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
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q fib`

### Question 2: Right Triangle

Write a function that takes in 3 sides `a`

, `b`

, and `c`

and checks to see if they can be possible lenths of the sides of a right triangle. Recall Pythagorean's Theorem:

`x^2 + y^2 = z^2 # where z is the hypotenuse`

Hint:Find the smallest and largest side first

```
def right_triangle(a, b, c):
"""Determine whether a, b, and c can be sides of a right triangle
>>> right_triangle(1, 1, 1)
False
>>> right_triangle(5, 3, 4)
True
>>> right_triangle(8, 10, 6)
True
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q right_triangle`

### Question 3: Disneyland Discounts

Disneyland is having a special where they give discounts for
grandparents accompanying their grandchildren. Help Disneyland figure
out when the discount should be given. Define a function
`gets_discount`

that takes two numbers as input (representing the two
ages) and returns `True`

if one of them is a senior citizen (age 65 or above)
and the other is a child (age 12 or below). You should not use `if`

in your
solution.

```
def gets_discount(x, y):
""" Returns True if this is a combination of a senior citizen
and a child, False otherwise.
>>> gets_discount(65, 12)
True
>>> gets_discount(9, 70)
True
>>> gets_discount(40, 45)
False
>>> gets_discount(40, 75)
False
>>> gets_discount(65, 13)
False
>>> gets_discount(7, 9)
False
>>> gets_discount(73, 77)
False
>>> gets_discount(70, 31)
False
>>> gets_discount(10, 25)
False
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q gets_discount`

### Question 4: 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
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q mul_by_num`

### Question 5: 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
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q count_cond`