CSC110 Fall 2025 Assignment 3

\( \newcommand{\NOT}{\neg} \newcommand{\AND}{\wedge} \newcommand{\OR}{\vee} \newcommand{\XOR}{\oplus} \newcommand{\IMP}{\Rightarrow} \newcommand{\IFF}{\Leftrightarrow} \newcommand{\TRUE}{\text{True}\xspace} \newcommand{\FALSE}{\text{False}\xspace} \newcommand{\IN}{\,{\in}\,} \newcommand{\NOTIN}{\,{\notin}\,} \newcommand{\TO}{\rightarrow} \newcommand{\DIV}{\mid} \newcommand{\NDIV}{\nmid} \newcommand{\MOD}[1]{\pmod{#1}} \newcommand{\MODS}[1]{\ (\text{mod}\ #1)} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\cA}{\mathcal A} \newcommand{\cB}{\mathcal B} \newcommand{\cC}{\mathcal C} \newcommand{\cD}{\mathcal D} \newcommand{\cE}{\mathcal E} \newcommand{\cF}{\mathcal F} \newcommand{\cG}{\mathcal G} \newcommand{\cH}{\mathcal H} \newcommand{\cI}{\mathcal I} \newcommand{\cJ}{\mathcal J} \newcommand{\cL}{\mathcal L} \newcommand{\cK}{\mathcal K} \newcommand{\cN}{\mathcal N} \newcommand{\cO}{\mathcal O} \newcommand{\cP}{\mathcal P} \newcommand{\cQ}{\mathcal Q} \newcommand{\cS}{\mathcal S} \newcommand{\cT}{\mathcal T} \newcommand{\cV}{\mathcal V} \newcommand{\cW}{\mathcal W} \newcommand{\cZ}{\mathcal Z} \newcommand{\emp}{\emptyset} \newcommand{\bs}{\backslash} \newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor} \newcommand{\bigfloor}[1]{\Big \lfloor #1 \Big \rfloor} \newcommand{\ceil}[1]{\left \lceil #1 \right \rceil} \newcommand{\bigceil}[1]{\Big \lceil #1 \Big \rceil} \newcommand{\abs}[1]{\left | #1 \right |} \newcommand{\bigabs}[1]{\Big | #1 \Big |} \newcommand{\xspace}{} \newcommand{\proofheader}[1]{\underline{\textbf{#1}}} \)

Note: Any FAQs or clarifications relevant to the assignment will be posted here. This post will be continually updated (with newer updates at the bottom of the page), so make sure to check on it regularly – click the “Watch” button in the top-right corner to receive notifications about this thread. If you have a question which is not already addressed on this page, create a new thread to post your question on Ed.

In this assignment, you apply what you’ve learned in the past few weeks about number theory, asymptotic function growth, and algorithm running time. In Part 1, you prove some mathematical statements involving familiar definitions. In Part 2, you use loop invariants to develop an interesting algorithm involving numbers and divisibility. And in Part 3, you analyze the running time of some code that we provide, as well as some code you wrote yourself.

Logistics

Starter files

General instructions

This assignment contains a mixture of both written and programming questions. All of your written work should be completed in the a3.tex starter file using the LaTeX typesetting language (hand-written work will not be graded). You went through the process of getting started with LaTeX in the software installation guide, but for a quick start we recommend using the online platform Overleaf for LaTeX. Overleaf also provides many tutorials to help you get started with LaTeX.

Your programming work should be completed in the starter file provided. We have provided code at the bottom of each file for running doctest examples and PythonTA on each file. We are not grading doctests on this assignment, but encourage you to add some as a way to understand each function we’ve asked you to complete. We are using PythonTA to grade your work, so please run that on the Python file you submit using the code we’ve provided in the main block.

Warning: one of the purposes of this assignment is to evaluate your understanding and mastery of the concepts that we have covered so far. So on this assignment, you may only use parts of the Python programming language that we have covered in the first 9 chapters of the course notes. Other parts are not allowed, and parts of your submissions that use them may receive a grade as low as zero for doing so.

Part 1: Proofs

First, complete this reading on a new proof technique (for this course, but you may have seen it in other courses already) called proof by contradiction.

Reading: proof by contradiction

Given a statement \(P\) to prove, rather than attempt to prove it directly we assume that its negation \(\neg P\) is true, and then use this assumption to prove a statement \(Q\) and its negation \(\neg Q\). We call \(Q\) and \(\neg Q\) the contradiction that arises from the assumption that \(P\) is false.

Why does this work? Essentially, we argue that if \(P\) is false, then statement \(Q\) must be true, but its negation \(\neg Q\) must also be true. But these two things can’t be true at the same time, and so our original assumption must be wrong!

Proofs by contradiction often take a bit more thought than other proof techniques, because it isn’t necessarily clear what the contradiction (statement \(Q\)) should be. As an example of a proof by contradiction, we present one particularly famous proof dating back to the Greek mathematician Euclid. This proof makes use of one of the most important theorems in number theory: the Fundamental Theorem of Arithmetic, which says that any integer greater than 1 can be written as a unique product of primes. For example:

\[\begin{align*} 2 &= 2 \\ 4 &= 2^2 \\ 100 &= 2^2 \cdot 5^2 \\ 1450 &= 2 \cdot 5^2 \cdot 19 \\ 8840 &= 2^3 \cdot 5 \cdot 13 \cdot 17 \\ \end{align*}\]

Now we can proceed with the proof by contradiction of the following theorem:

Theorem. There are infinitely many primes.

Proof. Assume that this statement is false, i.e., that there is a finite number of primes. Let \(k \in \N\) be the number of primes, and let \(p_1, p_2, \dots , p_k\) be the prime numbers. Our statement \(Q\) will be “for all \(n \in \N\), \(n\) is prime if and only if \(n\) is one of \(\{p_1, \dots , p_k\}\).” \(Q\) is true because of our assumption that there are a finite number of primes, and the definitions of \(k\) and \(p_1, \dots, p_k\). Now we will show that \(Q\) is false. Define the number \[ P = 1 + \prod_{i=1}^{k} p_i = 1 + p_1 \times p_2 \times \dots \times p_k. \] As \(P\) is greater than any of the primes in the set, \(P\) cannot be prime and there must be some prime \(p \neq P\) that divides \(P\), by the fundamental theorem of arithmetic.

If \(p\) is in the set \(\{p_1, \dots , p_k\}\), then \(p\) would divide both \(P\) and \(p_1 \times \dots \times p_k\), so it must divide its difference \(P - p_1 \times \dots \times p_k = 1\). However, no prime can divide 1, so \(p \notin \{p_1, \dots , p_k\}\). So then \(p\) is a prime that is not one of \(\{p_1, \dots, p_k\}\), and so \(Q\) is false. Contradiction!

□

For this part, complete the following four proofs. You may use any results presented in the course notes or in class, as long as you explictly name the result, for example by saying “by the GCD characterization theorem”, or “by the theorem from lecture 8B relating modular equivalence and remainders”.

Part 2: Generating Coprime Numbers

In lecture, we saw how more complex algorithms like the Extended Euclidean Algorithm can use while loops and variable updates in very non-obvious ways. To understand how these while loops actually accomplish a given computational task, we introduced loop invariants. In this part of the assignment, we explore the technique of using loop invariants in more detail to develop a new number-theoretic algorithm that is more efficient than a simple “brute force” approach.

Numbers coprime to 2 and 3

Let’s start with a simple problem: generating a sorted list of all positive integers up to a given limit that are coprime to both 2 and 3. Here is one possible implementation of such a function; our first goal will be to understand how this function works.

def coprime_to_2_and_3(n: int) -> list[int]:
    """Return the natural numbers less than n that are coprime to both 2 and 3.

    The returned list is sorted.

    Preconditions:
      - n >= 6

    >>> coprime_to_2_and_3(20)
    [1, 5, 7, 11, 13, 17, 19]

    Implementation note: negative list indexing accesses items at the end of
    the list. For all lists lst and integers i between 0 and len(lst) - 1
    inclusive, lst[-i] == lst[len(lst) - i].
    """
    nums_so_far = [1, 5]
    while nums_so_far[-2] + 6 < n:
        next_number = nums_so_far[-2] + 6
        nums_so_far.append(next_number)

    return nums_so_far

To prove that this algorithm works, we need to use some loop invariants to understand the while loop.

Together, these loop invariants allow us to conclude that nums_so_far is always a sorted list of the natural numbers between 1 and nums_so_far[-1] that are coprime to 2 and to 3. The loop ends when nums_so_far[-2] + 6 >= n; using these loop invariants, it is possible to prove (although we won’t do it here) that when the loop ends, nums_so_far consists of exactly the positive integers < n that are coprime to n.

Numbers coprime to a set of primes

The coprime_to_2_and_3 function can be changed to be more general. We can write a function called coprime_to_all that is not limited to finding the coprimes of just 2 and 3, but of a set of prime numbers. Below is a more fleshed out definition:

Notice that the first doctest example produces the same result as coprime_to_2_and_3 when n=20. Notice that the second doctest example allows the caller to specify a larger set of prime numbers (in this case: 2, 3, and 7).

Part 3: Running-Time Analysis

Next, you’ll conduct a few running-time analyses on some functions as well as the algorithms you studied and implemented in the previous part. Complete all your work for this part in a3.tex.

In your running-time analyses, you should provide the exact step count (e.g., \(n^2 + 2n + 4\), with no remaining summations left in the step count) with justification for this step count, as well as a Theta expression (e.g., \(\Theta(n^2)\)). This matches the style of running-time analysis we’ve seen in lecture.

Note: ceilings/floors may be necessary to get the exact number of steps.

Note: for big O/Omega, you should also provide upper/lower bounds on step counts with justification, then translate this directly to the big O or Omega expression.

Note: you do not need to provide any formal proof or even justification for translating the exact count to its associated Theta expression.

Submission instructions

Please proofread, test, and fix PythonTA errors in your work before your final submission!

Remember, you can submit your files multiple times before the due date. So you can aim to submit your work early, and if you find an error or a place to improve before the due date, you can still make your changes and resubmit your work.

After you’ve submitted your work, please give yourself a well-deserved pat on the back and do something fun or eat some chocolate or warm up under a blanket! Holy cat, you’ve just completed your last assignment for CSC110.