#!/usr/bin/env python
# coding: utf-8
# ASSIGNMENT CONFIG
generate: true
export_cell:
    pdf: false
# In[3]:


import matplotlib.pyplot as plt
import numpy as np
get_ipython().run_line_magic('matplotlib', 'inline')

# BEGIN QUESTION
name: q1
manual: false
points: 2
# **Question 1.** Write a function called `sieve` that takes in a positive integer `n` and returns a `set` of the prime numbers less than or equal to `n`. Use the Sieve of Eratosthenes to find the primes.
# BEGIN SOLUTION
# In[4]:


def sieve(n):
    """
    Generate a set of prime numbers less than or equal to a positive integer.
    """
    # BEGIN SOLUTION
    is_prime = [True for _ in range(n + 1)]
    p = 2
    while p ** 2 <= n:
        if is_prime[p]:
            for i in range(p ** 2, n + 1, p):
                is_prime[i] = False
        p += 1

    is_prime[0]= False
    is_prime[1]= False

    return set(i for i in range(n + 1) if is_prime[i])
    # END SOLUTION

# END SOLUTION# BEGIN TESTS
# In[5]:


sieve(1) == set()


# In[6]:


sieve(2) == {2}


# In[7]:


sieve(3) == {2, 3}


# In[8]:


# HIDDEN
sieve(20) == {2, 3, 5, 7, 11, 13, 17, 19}


# In[9]:


""" # BEGIN TEST CONFIG
points: 1
hidden: true
""" # END TEST CONFIG
sieve(100) == {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

# END TESTS# END QUESTION# BEGIN QUESTION
name: q2
manual: true
# **Question 2.** Evaluate the integral:
# 
# $$
# \int x e^x \, \mathrm dx
# $$
# BEGIN PROMPT
# $$
# \begin{aligned}
# \int x e^x \, \mathrm dx &= \texttt{# YOUR MATH HERE} \\
# \end{aligned}
# $$
# END PROMPT# BEGIN SOLUTION
# **SOLUTION:**
# 
# $$
# \begin{aligned}
# \int x e^x \, \mathrm dx &= x e^x - \int e^x \, \mathrm dx \\
# &= x e^x - e^x + C \\
# &= e^x (x - 1) + C \\
# \end{aligned}
# $$
# END SOLUTION# END QUESTION# BEGIN QUESTION
name: q3
manual: true
# **Question 3.** Graph the function $f(x) = \arctan \left ( e^x \right )$.
# BEGIN SOLUTION
# In[10]:


f = lambda x: np.arctan(np.exp(x))
xs = np.linspace(-10, 10, 100)
ys = f(xs)

plt.plot(xs, ys)
plt.xlabel("$x$")
plt.ylabel("$f(x)$")
plt.title(r"$f(x) = \arctan \left ( e^x \right )$");

# END SOLUTION# END QUESTION# BEGIN QUESTION
name: q4
manual: false
# **Question 4.** Write a function `hailstone` that returns the hailstone sequence for a positive integer ``n`` as a ``list``.
# BEGIN SOLUTION
# In[11]:


def hailstone(n):
    """
    Generate the hailstone sequence of a positive integer.
    """
    # BEGIN SOLUTION
    if n == 1:
        return [n]
    elif n % 2 == 0:
        return [n] + hailstone(n // 2)
    else:
        return [n] + hailstone(3 * n + 1)
    # END SOLUTION

# END SOLUTION# BEGIN TESTS
# In[19]:


hailstone(1) == [1]


# In[20]:


hailstone(2)  == [2, 1]


# In[22]:


hailstone(4) == [4, 2, 1]


# In[25]:


""" # BEGIN TEST CONFIG
points: 1.5
hidden: true
""" # END TEST CONFIG
hailstone(20) == [20, 10, 5, 16, 8, 4, 2, 1]


# In[27]:


""" # BEGIN TEST CONFIG
points: 1.5
hidden: true
""" # END TEST CONFIG
hailstone(9) == [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

# END TESTS# END QUESTION# BEGIN QUESTION
name: q5
manual: false
# **Question 5.** Write a function ``gcd`` that takes in two positive integers ``a`` and ``b`` and returns their greatest common divisor.
# BEGIN SOLUTION
# In[28]:


def gcd(a, b):
    """
    Find the GCD of two positive integers.
    """
    # BEGIN SOLUTION
    if a == 0:
        return b
    return gcd(b % a, a)
    # END SOLUTION

# END SOLUTION# BEGIN TESTS
# In[31]:


gcd(1, 1) == 1


# In[32]:


gcd(2, 1) == 1


# In[33]:


gcd(5, 5) == 5


# In[34]:


gcd(10, 4) == 2


# In[38]:


""" # BEGIN TEST CONFIG
points: 0.5
hidden: true
""" # END TEST CONFIG
gcd(121, 11) == 11


# In[37]:


""" # BEGIN TEST CONFIG
points: 0.5
hidden: true
""" # END TEST CONFIG
gcd(807306, 622896) == 4098

# END TESTS# END QUESTION