Homework 2: Control

Due: Tuesday 09/15 @ 11:59pm
Points: 1
Download: hw02.zip

To receive credit, you must solve each problem and then complete a short checkoff interview about your solution. You may use Preceptor for the interview or come to office hours to be interviewed by a member of the course staff. Staff will be doing in-person checkoffs for up to 3 business days after the assignment deadline (including any approved extension). If a checkoff happens more than 3 business days after the regular deadline, staff may ask to confirm your extended deadline via Flextensions. You will submit a Provenance bundle that includes a record of how you used VS Code, including interactions with Preceptor. Please do not use AI tools other than Preceptor for this assignment.

Readings: This homework relies on the following readings from Composing Programs:

Required Questions

Q1: Hailstone

Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.

Pick a positive integer n as the start.
If n is even, divide it by 2.
If n is odd, multiply it by 3 and add 1.
Continue this process until n is 1.

The number n will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried—nobody has ever proved that the sequence will terminate). Analogously, a hailstone travels up and down in the atmosphere before eventually landing on earth.

This sequence of values of n is often called a Hailstone sequence. Write a function that takes a single argument with formal parameter name n, prints out the hailstone sequence starting at n, and returns the number of steps in the sequence:

def hailstone(n):
    """Print the hailstone sequence starting at n and return its length.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    >>> b = hailstone(1)
    1
    >>> b
    1
    """
    "*** YOUR CODE HERE ***"

Hailstone sequences can get quite long! Try 27. What's the longest you can find?

Note that if n == 1 initially, then the sequence is one step long.
Hint: If you see 4.0 but want just 4, try using floor division // instead of regular division /.

python3 -m pytest -k hailstone

Fun fact: In 2019, there was a major development in understanding how the hailstone conjecture works for most numbers! This 2026 StarTalk interview with Terence Tao discusses the problem.

Q2: Abundant

Definitions:

A proper divisor of positive integer n is a positive integer smaller than n that evenly divides n.
A positive integer is abundant if it is smaller than the sum of of its proper divisors.

Implement a function abundant that takes a positive integer n. It prints all ways of multiplying two positive integers to make n, with the smaller factor first, ordered from the smallest first factor to the largest. Each pair is printed only once (so 3 * 4 is printed but 4 * 3 is not). It returns whether n is an abundant.

Hint: To print 1 * 2, write print(1, '*', 2).

def abundant(n):
    """Print all ways of forming positive integer n by multiplying two positive
    integers together, ordered by the first term. Then, return whether the sum
    of the proper divisors of n is greater than n.

    A proper divisor of n evenly divides n but is less than n.

    >>> abundant(12) # 1 + 2 + 3 + 4 + 6 is 16, which is larger than 12
    1 * 12
    2 * 6
    3 * 4
    True
    >>> abundant(14) # 1 + 2 + 7 is 10, which is not larger than 14
    1 * 14
    2 * 7
    False
    >>> abundant(16)
    1 * 16
    2 * 8
    4 * 4
    False
    >>> abundant(20)
    1 * 20
    2 * 10
    4 * 5
    True
    >>> abundant(22)
    1 * 22
    2 * 11
    False
    >>> r = abundant(24)
    1 * 24
    2 * 12
    3 * 8
    4 * 6
    >>> r
    True
    >>> abundant(25)
    1 * 25
    5 * 5
    False
    >>> abundant(156)
    1 * 156
    2 * 78
    3 * 52
    4 * 39
    6 * 26
    12 * 13
    True
    """
    "*** YOUR CODE HERE ***"

python3 -m pytest -k abundant

Submit

Run Provenance: Prepare Submission Bundle from the VS Code command palette to create your submission zip, and upload that zip to Gradescope. For a refresher on how to do this, refer to Lab 00.