Lesson 1 — Exercises: Introduction to Discrete Mathematics

Ex 1 Even vs Odd integers

Write a Python function classify(n: int) -> str that returns "even" if $n$ is even and "odd" otherwise.

The function must handle negative integers and zero correctly.
Verify: classify(0) == "even", classify(7) == "odd", classify(-4) == "even".
Print the classification for every integer in $[-3,0, 5, 10]$.

Hint: An integer $n$ is even iff $n \bmod 2 = 0$.

Ex 2 Primality Test primes

Implement is_prime(n: int) -> bool using trial division up to $\lfloor\sqrt{n}\rfloor$.

Handle edge cases: $n < 2$ is not prime; 2 is prime; even numbers $> 2$ are not prime.
List all primes below 30 and verify the result is [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].

Hint: Use math.isqrt(n) from the standard library to compute $\lfloor\sqrt{n}\rfloor$ exactly.

Ex 3 Modular Arithmetic mod

Write mod_ops(a, b, m) -> dict that returns a dictionary with keys "add", "sub", and "mul" holding $(a+b)\bmod m$, $(a-b)\bmod m$, and $(a \cdot b)\bmod m$ respectively.

Test with $a=17,\; b=9,\; m=5$.
Verify the distributive law for addition: $(a+b)\bmod m = \bigl((a\bmod m)+(b\bmod m)\bigr)\bmod m$.

Ex 4 GCD and LCM divisibility

Implement lcm(a, b) using Python's math.gcd, then verify the identity:

$$\gcd(a,b)\times \text{lcm}(a,b) = a \times b$$

Test with pairs $(12,8)$, $(100,75)$, and $(17,13)$. Print the GCD, LCM, and whether the identity holds for each pair.

Ex 5 Fibonacci Sequence sequences

Write fibonacci(n: int) -> list[int] that generates the first $n$ Fibonacci numbers iteratively (no recursion).

The sequence starts: $0, 1, 1, 2, 3, 5, 8, \ldots$ with recurrence $F(n) = F(n-1)+F(n-2)$.
Print the first 12 terms and verify your output matches: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89].

Hint: Handle the edge case $n \le 0$ by returning an empty list.

Ex 6 Counting Divisors divisibility

Write divisors(n: int) -> list[int] that returns all positive divisors of $n$ in sorted order.

Apply it to $n \in \{12, 16, 17, 36\}$ and print the divisors, their count, and whether $n$ is a perfect square.
Observe that perfect squares always have an odd number of divisors. Why?

Ex 7 Binomial Coefficient & Pascal's Identity combinatorics

Implement $C(n,k)$ (n-choose-k) without using math.comb, then verify Pascal's identity:

$$C(n,k) = C(n-1,k-1) + C(n-1,k)$$

Check that $C(5,2)=10$ and $C(6,3)=20$.
Assert Pascal's identity for all valid $(n,k)$ with $2 \le n \le 6$.

Hint: Use the multiplicative formula and reduce $k$ to $\min(k,\, n-k)$ to minimise iterations.

Ex 8 Power Set sets · counting

Write power_set(s: list) -> list that returns the list of all subsets of $s$.

Use itertools.combinations to enumerate subsets of each size $k = 0, 1, \ldots, |s|$.
Apply it to $S = \{1, 2, 3\}$ and verify that $|\mathcal{P}(S)| = 2^3 = 8$.

Ex 9 Sieve of Eratosthenes primes

Implement sieve(N: int) -> list[int] that returns all primes $\le N$ using the Sieve of Eratosthenes (boolean array).

Verify that there are exactly 168 primes below 1000.
Print the largest prime $\le 1000$.

Hint: Start crossing off multiples of $i$ from $i^2$, not from $2i$. Only iterate $i$ up to $\lfloor\sqrt{N}\rfloor$.

Ex 10 Arithmetic & Geometric Sequences sequences

Write arithmetic(start, step, n) and geometric(start, ratio, n) that each return a list of $n$ terms.

Generate the arithmetic sequence with $\text{start}=3,\;\text{step}=4,\; n=8$.
Verify the arithmetic sum formula: $S = \dfrac{n}{2}(a_1 + a_n)$.
Generate the geometric sequence with $\text{start}=2,\;\text{ratio}=3,\; n=6$.

Ex 11 Brute-Force Truth Table logic

Write brute_truth_table(expr_fn, var_names) that prints a truth table for any boolean function of $n$ variables by enumerating all $2^n$ combinations.

Use itertools.product([False, True], repeat=n) to generate rows.
Apply it to: $(p \to q) \leftrightarrow (\neg p \lor q)$ — this is a tautology.
Also apply it to: $(p \land q) \lor (\neg p \land \neg q)$ — this is the truth table for $p \leftrightarrow q$.

Lesson 1 — Introduction to Discrete Mathematics