Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · Grades 6–8

Programming for mathematics

Name: ______________________

Date: ______________________

You will learn to

Write programs with variables, loops, conditionals and functions to compute sums, tables and sequences
Explain the difference between assignment (= in a program) and equality in mathematics
Use a program to test a conjecture on many cases, and explain why this is evidence but not proof, while one counterexample is a disproof
Convert between decimal and binary by hand and in code, and explain why every whole number has exactly one binary representation without leading zeros
Explain why 0.1 + 0.2 == 0.3 is False in Python, and use exact fractions instead

1.
What is the value of x after these three lines run?
```
x = 3
x = x + 4
x = 2 * x
```
2.
What does the Python line count = count + 1 do?
- A.It increases the value stored in count by $1$
- B.Nothing, because the equation $c = c + 1$ has no solution
- C.It causes an error, because count appears on both sides
- D.It tests whether count equals count + 1
3.
Write the binary number $110101_2$ in decimal.
4.
Write $26$ in binary, without leading zeros. (Type just the digits, for example 101.)

What does this program print?

total = 0
for i in range(1, 6):
    if i % 2 == 1:
        total = total + i
print(total)

6.
In Python, 0.1 + 0.2 == 0.3 evaluates to False. Why?
- A. $0.1$ and $0.2$ cannot be stored exactly in binary, so the computer adds two slightly wrong numbers
- B.It is a bug in Python that will be fixed in a later version
- C.Python rounds every decimal to a whole number
- D.Python adds from right to left, so the order is wrong
7.
The uniqueness proof for binary representations starts: “the last binary digit of $n$ must be the remainder of $n$ on division by $2$ ”. Why is that true?
- A.Every other digit stands for an even amount ( $2, 4, 8, \dots$ ), so only the last digit decides whether $n$ is even or odd
- B.Because we define the last digit to be the remainder
- C.Because the last digit is the smallest digit
- D.Because binary numbers always end in $1$
8.
Write to_binary(n) that returns the binary representation of a whole number n as a string without leading zeros, using repeated division by 2 (don't use Python's built-in bin). to_binary(0) should be "0".
Computational — Practice
9.
This function is meant to compute $1^2 + 2^2 + \dots + n^2$ . It runs without any error — but it is wrong. Find and fix the bug. Then check your fixed version against the formula $\tfrac{n(n + 1)(2n + 1)}{6}$ .
Computational — Practice
10.
In the Lean section, which of these machine-checked statements tells you that the sum $1 + 2 + \dots + 1000$ equals $\tfrac{1000 \cdot 1001}{2}$ ?
- A.gauss_formula : 2 * sumTo n = n * (n + 1) (proved by induction)
- B.loop_agrees_tested : ∀ n, n < 40 → sumFor n = sumTo n (proved by running both programs)
- C.sum_for_examples : sumFor 10 = 55 ∧ sumFor 100 = 5050
- D.sum_odds_eq_square : sumOdds n = n * n

Answer key — Programming for mathematics

1.
Line by line: x is $3$ , then $3 + 4 = 7$ , then $2 \cdot 7 = 14$ . Each assignment replaces the stored value, using the value from the line before.
2.
It is an assignment: Python computes count + 1 from the current value and stores the result in count. So if count was $4$ , it becomes $5$ . As an equation, $c = c + 1$ would have no solution — which is exactly why programs and algebra use the symbol differently.
3.
$110101_2 = 1 \cdot 32 + 1 \cdot 16 + 0 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 53$ . Or read from the left, doubling and adding: $1, 3, 6, 13, 26, 53$ .
4.
$26 = 2 \cdot 13 + 0$ , $13 = 2 \cdot 6 + 1$ , $6 = 2 \cdot 3 + 0$ , $3 = 2 \cdot 1 + 1$ , $1 = 2 \cdot 0 + 1$ . Reading the remainders from the bottom up: $26 = 11010_2$ . Check: $16 + 8 + 2 = 26$ .
5.
The loop runs for $i = 1, 2, 3, 4, 5$ , and adds $i$ only when it is odd: $1 + 3 + 5 = 9$ . (Notice that the answer is $3^2$ — the sum of the first three odd numbers.)
6.
In binary, $\tfrac{1}{10} = 0.000110011\ldots_2$ repeats for ever, just as $\tfrac{1}{3} = 0.333\ldots$ does in decimal. A floating-point number keeps only 53 binary digits, so $0.1$ , $0.2$ and $0.3$ are each stored with a tiny error, and the errors do not cancel: 0.1 + 0.2 is stored as 0.30000000000000004. For exact answers use Fraction(1, 10) + Fraction(2, 10) == Fraction(3, 10), which is True.
7.
In $n = d_k 2^k + \dots + d_1 \cdot 2 + d_0$ , every term except $d_0$ is a multiple of $2$ . So $n = 2m + d_0$ for a whole number $m$ , with $d_0 \in \{0, 1\}$ , which means $d_0$ is the remainder of $n$ on division by $2$ . Any two representations of $n$ therefore have the same last digit, which is the first step of the uniqueness proof.
8.
```
def to_binary(n):
    if n == 0:
        return "0"
    digits = ""
    while n > 0:
        digits = str(n % 2) + digits
        n = n // 2
    return digits
```
Each pass of the loop writes $n = 2q + r$ , records the remainder $r$ as the next digit from the right, and continues with $q$ . The loop stops because $q < n$ whenever $n \ge 1$ . Theorem 2 says the result is the only binary representation of $n$ without leading zeros.
9.
```
def sum_of_squares(n):
    total = 0
    for i in range(1, n + 1):
        total = total + i * i
    return total
```
The original loop used range(1, n), which stops at $n - 1$ , so it left out $n^2$ : sum_of_squares(3) gave $1 + 4 = 5$ instead of $14$ . Nothing crashed — the program did exactly what it was told. Comparing with a case worked out by hand, or with a proven formula, is how such bugs are caught. (The formula $\tfrac{n(n+1)(2n+1)}{6}$ can itself be proved by induction, like Theorem 1.)
10.
gauss_formula is a theorem about every $n$ , proved by induction, so it gives $2 \cdot (1 + \dots + 1000) = 1000 \cdot 1001$ , i.e. the sum is $500\,500$ . The tested statement and the examples are machine-checked too — but only for the cases that were actually computed.