Notebook # ASSIGNMENT CONFIG generate: true export_cell: pdf: false

In [3]:

import matplotlib.pyplot as plt
import numpy as np
%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()

Out[5]:

True

In [6]:

sieve(2) == {2}

Out[6]:

True

In [7]:

sieve(3) == {2, 3}

Out[7]:

True

In [8]:

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

Out[8]:

True

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}

Out[9]:

True

# 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]

Out[19]:

True

In [20]:

hailstone(2)  == [2, 1]

Out[20]:

True

In [22]:

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

Out[22]:

True

In [25]:

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

Out[25]:

True

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]

Out[27]:

True

# 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

Out[31]:

True

In [32]:

gcd(2, 1) == 1

Out[32]:

True

In [33]:

gcd(5, 5) == 5

Out[33]:

True

In [34]:

gcd(10, 4) == 2

Out[34]:

True

In [38]:

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

Out[38]:

True

In [37]:

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

Out[37]:

True

# END TESTS# END QUESTION