Say it once, do it many times
At a robot club in Cairo, Yasmin is programming a little floor robot to drive round a square mat. She types:
forward, turn right, forward, turn right, forward, turn right, forward, turn right
Eight instructions. Her friend Omar laughs. "You said the same thing four times! Why not just say: repeat 4 times: forward, turn right?"
That one line does the same job as all eight instructions. And if Yasmin wants the robot to go round the mat ten times, she does not have to type 80 instructions — she just changes 4 into 40.
Later the robot has to cross a pretend road on the mat. "Go when it's safe" is not precise enough for a robot. Yasmin writes: if the light is green, then go forward; otherwise, wait. Now the robot can make a decision.
Repeating and deciding
You already know how to follow a program — a list of instructions done one after another (see Following and giving precise instructions). Two new ideas make programs much more powerful.
Repeating. Many tasks do the same thing again and again: clap, stamp, clap, stamp…; stir, wait, stir, wait…; add the next column, add the next column… A loop says the repeated part once, and says how many times to repeat it — or when to stop.
Deciding. Some tasks depend on what is happening: if it is raining, take an umbrella; if the number is even, put it in the left box. A condition is a statement that is either true or false, like "the light is green" (see True, false, and, or, not). An if–then rule uses a condition to choose what to do.
Big ideas
Definition— loop
A loop repeats a block of instructions. A repeat-times loop repeats it a fixed number of times: "repeat 4 times: forward, turn right". A repeat-until loop repeats it until a condition becomes true: "repeat: add 3, until the number is bigger than 20".
Definition— condition
A condition is a statement that is either true or false, such as "the number is even" or "the light is green". It is used to decide which instructions to follow, or when to stop a loop.
Definition— if–then–otherwise
An if–then–otherwise rule says: if the condition is true, then do one thing; otherwise (if it is false) do another. Rules can be chained: "if …, then …; otherwise, if …, then …; otherwise …". They are checked in order, and the first true condition wins.
Definition— algorithm
An algorithm is a precise list of steps for doing a task, which can use loops and decisions. Following an algorithm needs no guessing.
Let's try together
Example— Shapes from loops
- Square: repeat 4 times: forward, turn right 90°.
- Equilateral triangle: repeat 3 times: forward, turn right 120°.
- Regular hexagon: repeat 6 times: forward, turn right 60°.
- Five-pointed star: repeat 5 times: forward, turn right 144°.
In each closed shape the robot ends where it started, facing the same way. Count up its turning: , , — one whole turn. The star is special: , two whole turns!
Example— Repeat until
"Start at 0. Repeat: add 3, until the number is bigger than 20."
. Now 21 is bigger than 20, so the loop stops. "Add 3" was done 7 times.
The loop checks the condition each time round. It does not know in advance how many times it will repeat — it just keeps going until the condition is true.
Example— If–then rules for sorting
Neema sorts number cards into three boxes with these rules, checked in order:
- If the number is bigger than 50, then put it in the red box;
- otherwise, if the number is even, then put it in the blue box;
- otherwise, put it in the yellow box.
The card 64 goes in the red box (rule 1 is true, so we stop there). The card 18 goes in blue: rule 1 is false, rule 2 is true. The card 7 goes in yellow: rules 1 and 2 are both false. Every card ends up in exactly one box.
Example— FizzBuzz: a game with decisions
Players count in turn, 1, 2, 3, … but with these rules:
- if the number is a multiple of 3 and of 5, say "FizzBuzz";
- otherwise, if it is a multiple of 3, say "Fizz";
- otherwise, if it is a multiple of 5, say "Buzz";
- otherwise, say the number.
So the game goes: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, …
The order of the rules matters. If we checked "multiple of 3?" first, then 15 would get "Fizz" — and nobody would ever say "FizzBuzz", because every multiple of 15 is also a multiple of 3. The whole game is a loop ("for each number, …") with decisions inside.
Example— Column addition is a loop
Here is the written method for adding two numbers, as an algorithm:
- Start with a carry of 0.
- Repeat for each column, from the ones column to the left:
- add the two digits and the carry;
- if the total is 10 or more, then write down the total minus 10 and carry 1;
- otherwise, write down the total and carry 0.
- At the end, if the carry is 1, write it down.
For :
| column | digits + carry | total | write | carry |
|---|---|---|---|---|
| ones | 13 | 3 | 1 | |
| tens | 14 | 4 | 1 | |
| hundreds | 6 | 6 | 0 |
The answer is 643. A loop (one pass per column) with a decision inside (carry or not)!
Why the loops work
Theorem— The square loop comes home
"Repeat 4 times: forward 1 square, turn right 90°" brings the robot back to where it started, facing the same way.
Proof
Each pass of the loop moves one square and then turns a quarter turn to the right. So the four moves go up, right, down, left, in that order. The one step up is cancelled by the one step down, and the one step right by the one step left, so the robot is back where it started. It has turned four quarter turns, which make one whole turn, so it faces the same way as at the start.
∎
Theorem— The carry is never more than 1
When we add two numbers by the column method, the carry into each column is always 0 or 1.
Proof
The carry into the ones column is 0. Now suppose the carry into some column is 0 or 1. The two digits in that column are each at most 9, so the column total is at most . A total of at most 19 is less than 20, so it contains at most one ten: the carry into the next column is again 0 or 1. Going from column to column, the carry stays 0 or 1 all the way along.
∎
Why column addition gives the right answer. In each column we add the digits in that place: ones with ones, tens with tens, and so on. When a column total is 10 or more, say 13 ones, we write the 3 ones down and move the ten to the tens column, where it counts as 1 ten. Nothing is lost and nothing is added: we are just regrouping ten ones as one ten, or ten tens as one hundred. So the digits we write down make exactly the sum.
Theorem— A loop that never stops
"Start at 9. Repeat: take away 2, until the number is exactly 0." This loop never stops.
Proof
The loop starts at 9, which is odd. Taking 2 away from an odd number always gives another odd number (9, 7, 5, 3, 1, −1, −3, …). So the number is always odd. But 0 is even, so the number is never 0: the stopping condition can never become true, and the loop goes on for ever.
∎
This is a bug. To fix it, change the condition to one that will become true: "until the number is less than 1" stops after 5 steps, at . Or start at an even number: from 10 the loop reaches 0 after 5 steps.
Explore: watch the loops run
Here the column addition loop runs on base-ten blocks, one column at a time. Watch what happens when a column has 10 or more: ten ones are traded for one ten — that is the carry. Then type your own numbers.
368 + 275, one column at a time
Step through. Which columns carry? Why is the carry never 2?
- from 368
- from 275
- regrouped
Hundreds
5
Tens
13
Ones
13
Step 1 of 7
368 + 275
Show 368 and 275 with blocks. We add one column at a time, starting with the ones on the right.
A repeating pattern is a loop that runs on and on: "repeat for ever: circle, triangle, square". Change the core of the pattern, then predict which shape is item number 20 before you check. (Hint: how many times does the loop go all the way round before item 20?)
A loop of shapes
Predict item 20, then item 50. How does the remainder help?
The core: the part that repeats
Tap a shape to add it to the core:
The pattern
- A1
- B2
- C3
- A4
- B5
- C6
- A7
- B8
- C9
- A10
- B11
- C12
- A13
- B14
- C15
What is item number 20?
Gideon's true-or-false game
Gideon only plays with statements that are exactly true or exactly false. Decide, and give a reason.
- "Repeat 4 times: forward, turn right is the same as writing those two instructions out 4 times." — True. That is what the loop means: 8 instructions.
- "Repeat 3 times: forward, turn right brings the robot home." — False. It walks three sides of the square and stops one square away.
- "In FizzBuzz, the number 30 is said as 'Fizz'." — False. 30 is a multiple of 3 and of 5, and that rule is checked first: "FizzBuzz".
- "In column addition, the carry can be 2." — False. A column total is at most .
- "Start at 9, take away 2 until you reach exactly 0 stops after a while." — False. The number is always odd, so it is never 0.
For grown-ups · the same ideas in Lean, a proof checker
The robot's instructions, a program runner, and the loop "repeat n times":
/-- The robot's two instructions. -/
inductive Instr where
| forward | turnRight
deriving DecidableEq, Repr/-- Follow a whole program, one instruction after another. -/
def run (r : Robot) : List Instr → Robot
| [] => r
| i :: is => run (step r i) is/-- The loop "repeat `n` times: `block`", written out as a long program. -/
def repeatBlock : Nat → List Instr → List Instr
| 0, _ => []
| n + 1, block => block ++ repeatBlock n block/-- The 3-line loop "repeat 4 times: forward, turn right" is the same as the 8-instruction
program written out in full. -/
theorem square_loop :
repeatBlock 4 [.forward, .turnRight] =
[.forward, .turnRight, .forward, .turnRight, .forward, .turnRight, .forward, .turnRight] :=
rfl/-- **The square loop brings the robot home**: back at `(0, 0)`, facing north again. -/
theorem square_returns : run home (repeatBlock 4 [.forward, .turnRight]) = home := by
decide/-- The number of repeats matters: after only 3 repeats the robot is at `(1, 0)`, facing
west — three sides of the square, not home. -/
theorem three_repeats_not_home :
run home (repeatBlock 3 [.forward, .turnRight]) = ⟨1, 0, .west⟩ := by
decideFacts about every loop: repeating times is repeating times and then times, and a loop written out in full is long. Going round the square twice also comes home — proved without running it, from the square and the splitting rule:
/-- "Repeat `m + n` times" is "repeat `m` times" followed by "repeat `n` times". -/
theorem repeat_add (m n : Nat) (block : List Instr) :
repeatBlock (m + n) block = repeatBlock m block ++ repeatBlock n block := by
induction m with
| zero => simp [repeatBlock]
| succ m ih => rw [Nat.succ_add, repeatBlock, repeatBlock, ih, List.append_assoc]/-- Written out in full, "repeat `n` times" a block of `k` instructions has `n × k`
instructions. A loop saves a lot of writing! -/
theorem repeat_length (n : Nat) (block : List Instr) :
(repeatBlock n block).length = n * block.length := by
induction n with
| zero => simp [repeatBlock]
| succ n ih => rw [repeatBlock, List.length_append, ih, Nat.succ_mul, Nat.add_comm]/-- Going round the square twice is the loop "repeat 8 times": it also brings the robot
home — because it is the square loop followed by the square loop. -/
theorem eight_returns : run home (repeatBlock 8 [.forward, .turnRight]) = home := by
rw [show 8 = 4 + 4 from rfl, repeat_add, run_append, square_returns, square_returns]Decisions. FizzBuzz is a chain of if … then … else. Lean checks the first fifteen turns, proves that "FizzBuzz" is said exactly for multiples of 3 and 5 — for every number — and proves that the buggy order never says it at all:
/-- The FizzBuzz rule, as `if … then … else` decisions, checked in this order: multiple of 3
and of 5 (that is, of 15)? multiple of 3? multiple of 5? otherwise the number itself. -/
def fizzBuzz (n : Nat) : Say :=
if n % 15 = 0 then .fizzBuzz
else if n % 3 = 0 then .fizz
else if n % 5 = 0 then .buzz
else .number n/-- The loop "for each number from 1 to 15: say `fizzBuzz n`". -/
theorem fizzBuzz_to_fifteen :
(List.range' 1 15).map fizzBuzz =
[.number 1, .number 2, .fizz, .number 4, .buzz, .fizz, .number 7, .number 8, .fizz,
.buzz, .number 11, .fizz, .number 13, .number 14, .fizzBuzz] := by
decide/-- The rule says "FizzBuzz" **exactly** for the numbers that are multiples of 3 **and** of 5 —
for every number, not just the first fifteen. -/
theorem fizzBuzz_iff (n : Nat) : fizzBuzz n = .fizzBuzz ↔ n % 3 = 0 ∧ n % 5 = 0 := by
unfold fizzBuzz
split
· constructor
· intro _
omega
· intro _
rfl
· split
· simp only [reduceCtorEq, false_iff]
omega
· split
· simp only [reduceCtorEq, false_iff]
omega
· simp only [reduceCtorEq, false_iff]
omega/-- **The order of the conditions matters.** The buggy version never says "FizzBuzz": every
multiple of 15 is a multiple of 3, so the first condition always catches it. -/
theorem buggy_never_fizzBuzz (n : Nat) : fizzBuzzBuggy n ≠ .fizzBuzz := by
unfold fizzBuzzBuggy
split
· simp
· split
· simp
· split
· omega
· simpColumn addition. Numbers are lists of digits, ones first; the algorithm loops over the columns with a carry. The theorem addColumns_correct proves that the method gives the right answer for every pair of numbers, using exactly the regrouping idea above: a column total is .
/-- The value of a list of digits written **ones first**: `[3, 4, 6]` means
3 + 10 × 4 + 100 × 6 = 643. -/
def value : List Nat → Nat
| [] => 0
| d :: ds => d + 10 * value ds/-- **Column addition.** The columns are pairs (top digit, bottom digit), ones column first.
Loop over the columns: add the two digits and the carry, write down the ones digit of the
total, and carry the tens to the next column. At the end, write down the last carry if it is
not 0. -/
def addColumns : List (Nat × Nat) → Nat → List Nat
| [], carry => if carry = 0 then [] else [carry]
| (a, b) :: rest, carry =>
(a + b + carry) % 10 :: addColumns rest ((a + b + carry) / 10)/-- 368 + 275: ones 8 + 5 = 13 (write 3, carry 1); tens 6 + 7 + 1 = 14 (write 4, carry 1);
hundreds 3 + 2 + 1 = 6. The answer is 643 (written ones first: `[3, 4, 6]`). -/
theorem example_368_275 :
addColumns [(8, 5), (6, 7), (3, 2)] 0 = [3, 4, 6] ∧ value [3, 4, 6] = 368 + 275 := by
decide/-- **Column addition is correct**, for every list of columns and every starting carry: the
value of the answer is the value of the top row plus the value of the bottom row plus the
carry. In each column the total `t` is split as `t = (t % 10) + 10 × (t / 10)`: the ones digit
stays, and the tens move one column left, where they are worth 10 times as much. -/
theorem addColumns_correct (cols : List (Nat × Nat)) (carry : Nat) :
value (addColumns cols carry) =
value (cols.map Prod.fst) + value (cols.map Prod.snd) + carry := by
induction cols generalizing carry with
| nil =>
simp only [addColumns, List.map_nil]
split
· simp only [value]
omega
· simp only [value]
omega
| cons p rest ih =>
obtain ⟨a, b⟩ := p
simp only [addColumns, value, List.map_cons, ih]
omega/-- With digits 0–9 and a carry of 0 or 1, a column total is at most 9 + 9 + 1 = 19, so the
next carry is again 0 or 1. -/
theorem carry_le_one (a b c : Nat) (ha : a ≤ 9) (hb : b ≤ 9) (hc : c ≤ 1) :
(a + b + c) / 10 ≤ 1 := by
omega"Repeat until" loops. Lean insists that every function finishes, so a repeat-until loop gets a fuel tank and gives up when the fuel runs out:
/-- "Repeat `act` until `stop` is true", starting from `n`. Lean only accepts functions that
always finish, so the loop gets a fuel tank: it gives up after `fuel` steps. The answer is the
final number and the number of steps taken. -/
def repeatUntil (stop : Int → Bool) (act : Int → Int) : Nat → Int → Int × Nat
| 0, n => (n, 0)
| fuel + 1, n =>
if stop n then (n, 0)
else
let r := repeatUntil stop act fuel (act n)
(r.1, r.2 + 1)/-- "Start at 0; repeat 'add 3' until the number is bigger than 20": it stops at 21 after
7 steps. -/
theorem count_up : repeatUntil (fun m => m > 20) (· + 3) 100 0 = (21, 7) := by
decide/-- "Start at 9; repeat 'take away 2' until the number is less than 1": it stops at −1 after
5 steps (9, 7, 5, 3, 1, −1). -/
theorem count_down_fixed : repeatUntil (fun m => m < 1) (· - 2) 100 9 = (-1, 5) := by
decide/-- Why "start at 9, take away 2 until you reach **exactly** 0" never stops: after `k` steps
the number is `9 − 2 × k`, which is odd, so it is never 0. -/
theorem odd_minus_twos (k : Nat) : (9 : Int) - 2 * k ≠ 0 := by
omega/-- The same fact about the loop itself: starting from **any odd number**, "take away 2 until
the number equals 0" uses up **all** of its fuel, however big the tank. The stopping condition
is never true, so on its own the loop would run for ever. -/
theorem never_stops (fuel : Nat) (n : Int) (h : n % 2 = 1) :
(repeatUntil (fun m => m == 0) (· - 2) fuel n).2 = fuel := by
induction fuel generalizing n with
| zero => rfl
| succ fuel ih =>
have hne : n ≠ 0 := by omega
simp [repeatUntil, hne, ih (n - 2) (by omega)]The last theorem is the odd-number proof: from any odd start, "take away 2 until exactly 0" burns all its fuel, however much it is given. What is not formalised: the turtle's angles (the Lean robot only makes quarter turns), and the general question of whether any program stops — which, as Alan Turing showed, no algorithm can answer for every program.
Margaret runs the loops
"""Column addition as a loop with a carry.
The written method for adding whole numbers is a loop over the columns,
from the ones column leftwards: add the two digits and the carry, write
down the ones digit of the total, and carry the tens into the next column.
The program shows every pass of the loop for 368 + 275, then checks the
method against ordinary addition for every pair of numbers below 200 and
for 2000 random pairs of numbers with up to 12 digits, recording the
largest column total and the largest carry ever seen.
"""
import random
import textwrap
PLACES = ["ones", "tens", "hundreds", "thousands"]
def digits_ones_first(n):
"""The digits of n, ones digit first: 368 -> [8, 6, 3]."""
out = []
while n > 0:
out.append(n % 10)
n //= 10
return out
def column_add(a, b):
"""Column addition of a and b.
Returns (answer, steps); each step is (top, bottom, carry_in, total,
written, carry_out), one per pass of the loop."""
top, bottom = digits_ones_first(a), digits_ones_first(b)
columns = max(len(top), len(bottom))
carry, written, steps = 0, [], []
for i in range(columns):
t = top[i] if i < len(top) else 0
u = bottom[i] if i < len(bottom) else 0
total = t + u + carry
if total >= 10:
digit, new_carry = total - 10, 1
else:
digit, new_carry = total, 0
steps.append((t, u, carry, total, digit, new_carry))
written.append(digit)
carry = new_carry
if carry:
written.append(carry)
answer = sum(d * 10 ** i for i, d in enumerate(written))
return answer, steps
def check_pairs(pairs):
"""(all answers right?, largest column total, largest carry) for pairs."""
right, top_total, top_carry = True, 0, 0
for a, b in pairs:
answer, steps = column_add(a, b)
right = right and answer == a + b
for step in steps:
top_total = max(top_total, step[3])
top_carry = max(top_carry, step[5])
return right, top_total, top_carry
def main():
answer, steps = column_add(368, 275)
print("368 + 275, one pass of the loop per column:")
for place, (t, u, c, total, digit, carry) in zip(PLACES, steps):
print(f" {place:<9} {t} + {u} + carry {c} = {total:>2}"
f" -> write {digit}, carry {carry}")
print(f" answer: {answer}")
print()
small = [(a, b) for a in range(200) for b in range(200)]
rng = random.Random(2024)
big = [(rng.randrange(10 ** 12), rng.randrange(10 ** 12))
for _ in range(2000)]
for label, pairs in [("all pairs below 200", small),
("2000 random pairs, up to 12 digits", big)]:
right, total, carry = check_pairs(pairs)
print(f"Checking {label}:")
print(f" every answer right: {right}; largest column total: {total};"
f" largest carry: {carry}")
print()
print(textwrap.fill(
"Epistemic status: exact arithmetic. Exhaustive for the 40000 pairs "
"of numbers below 200; for big numbers only a seeded random sample "
"of 2000 pairs was checked, which is evidence, not proof. The "
"lesson's place-value argument, and the Lean proof, show that the "
"method is right for every pair and that the carry is never more "
"than 1 (because 9 + 9 + 1 = 19).",
width=78,
))
if __name__ == "__main__":
main()Every answer agreed, the biggest column total was 19, and the carry was never more than 1 — just as the proof says. The checks of small numbers are exhaustive; the big numbers are only a sample, so they are evidence. The proof covers every pair.
"""Loops that close, loops that stop, and a loop that never stops.
A turtle starts at a point facing up and runs the loop 'repeat n times:
forward 1, turn right by some angle'. The program reports how far from the
start it finishes and how much it has turned altogether: the path closes
up when the total turning is a whole number of full turns (360 degrees).
Then it runs three 'repeat until' loops: counting up by 3 until the number
is bigger than 20, counting down by 2 from 10 until it is exactly 0, and
counting down by 2 from 9 until it is exactly 0 - a loop whose stopping
condition is never true, so the program has to give up after 1000 steps.
"""
import math
import textwrap
def turtle_loop(repeats, angle):
"""Run 'repeat: forward 1, turn right angle'. Return (end, total turn)."""
x, y, heading = 0.0, 0.0, 90.0 # heading in degrees; 90 means 'up'
for _ in range(repeats):
x += math.cos(math.radians(heading))
y += math.sin(math.radians(heading))
heading -= angle # turning right is clockwise
return (x, y), repeats * angle
def repeat_until(start, step, stop, limit=1000):
"""Repeat 'number = step(number)' until stop(number) is true.
Returns (final number, steps taken, stopped?) - gives up after limit."""
number = start
for steps in range(limit):
if stop(number):
return number, steps, True
number = step(number)
return number, limit, stop(number)
def main():
print("repeat n times: forward 1, turn right by a degrees")
print(" n a distance from start total turning")
for repeats, angle in [(4, 90), (3, 120), (6, 60), (3, 60), (5, 144),
(8, 45)]:
(x, y), turned = turtle_loop(repeats, angle)
distance = math.hypot(x, y)
print(f"{repeats:>4} {angle:>4} {distance:>19.3f} {turned:>9} deg")
print("Here the path closes exactly when the total turning is a whole")
print("number of full turns: 360, 720, ... degrees.")
print()
print("repeat until:")
loops = [
("start 0, add 3 until bigger than 20", 0, lambda n: n + 3,
lambda n: n > 20),
("start 10, take 2 until exactly 0", 10, lambda n: n - 2,
lambda n: n == 0),
("start 9, take 2 until exactly 0", 9, lambda n: n - 2,
lambda n: n == 0),
]
for text, start, step, stop in loops:
number, steps, stopped = repeat_until(start, step, stop)
if stopped:
print(f" {text}: stops after {steps} steps at {number}")
else:
print(f" {text}: gave up after {steps} steps (at {number})")
print()
print(textwrap.fill(
"Epistemic status: the turtle distances are floating-point "
"calculations, rounded to 3 decimal places, so '0.000' means 'zero "
"up to rounding' - the lesson explains with angles why these paths "
"close exactly. The counting loops use exact whole numbers. Giving "
"up after 1000 steps does not prove that a loop never stops; the "
"odd-number argument in the lesson does.",
width=78,
))
if __name__ == "__main__":
main()Look at the last line: the loop from 9 was still going after 1,000 steps. That does not prove it never stops — maybe it would stop after 1,001 steps? The odd-number argument is what proves it: the number is always odd, so it is never 0.
Your turn
Act the loops out: walk a square, play FizzBuzz with a friend, add in columns. You can ask for a hint whenever you like.
1. Repetition and decisions
Warm-upHumanThe loop repeat 5 times: forward, turn right, clap is written out in full, one instruction after another. How many instructions is that?
2. Repetition and decisions
CoreHumanWhich program makes the turtle draw an equilateral triangle (three equal sides, ending where it started)?
3. Repetition and decisions
CoreHumanThe program repeat 6 times: forward, turn right ☐ degrees draws a regular hexagon. What number goes in the box?
4. Repetition and decisions
CoreHumanStart at 5. Repeat: add 4, until the number is bigger than 30. How many times is "add 4" done?
5. Repetition and decisions
CoreHumanWhich of these loops never stops?
6. Repetition and decisions
CoreHumanIn FizzBuzz (FizzBuzz for multiples of 3 and 5; otherwise Fizz for multiples of 3; otherwise Buzz for multiples of 5; otherwise the number), which numbers from 1 to 20 are said as "Fizz"? Write them separated by commas, like {1, 2}.
7. Repetition and decisions
CoreHumanAdd 476 + 358 with the column method. How many times do you carry 1?
8. Repetition and decisions
StretchHumanWhen you add two numbers with the column method, why is the carry never 2?
9. Repetition and decisions
StretchFormalIn Lean, run home p is where the robot ends up after following program p from home, and repeatBlock 4 [.forward, .turnRight] is the loop "repeat 4 times: forward, turn right". Which statement says that the square loop brings the robot home?
10. Repetition and decisions
StretchComputationalWrite a function fizzbuzz(n) that returns what a player says for the number n: "FizzBuzz" for multiples of 3 and 5, otherwise "Fizz" for multiples of 3, otherwise "Buzz" for multiples of 5, otherwise the number as text (for example "7"). In Python, n % 3 == 0 is the condition "n is a multiple of 3".
Things that trip people up
Misconception
"A loop runs for ever, or just once." A repeat-times loop runs exactly as many times as it says: "repeat 4 times" runs 4 times. A repeat-until loop runs until its condition is true — sometimes 0 times (if the condition is already true at the start), sometimes 7 times, sometimes more.
Misconception
Writing a stopping condition that can never become true. "Start at 9, take away 2 until you reach exactly 0" never stops, because the number is always odd. Always ask: will the condition become true? Conditions like "until the number is less than 1" are safer than "until it is exactly 0".
Misconception
"The order of if–then rules doesn't matter." The rules are checked in order and the first true one wins. Checking "multiple of 3?" before "multiple of 15?" means FizzBuzz is never said.
Misconception
"To draw a triangle, turn 60°." The robot turns through the angle outside each corner. For an equilateral triangle that is 120°. A 60° turn makes part of a hexagon instead.
Other ways of seeing
Computation— The computer scientist: will it ever stop?
Margaret's computer had to give up on the loop from 9 — it could not tell by itself that the loop would never stop. Could a cleverer program look at any program and decide whether it will stop? In 1936 Alan Turing proved that no program can do this correctly for every program. This is called the halting problem, and it is one of the most famous results about what computers can and cannot do — see Computability. For a particular loop, though, a person can often find a proof, like our odd-number argument.
Geometry— The geometer: the turtle turns all the way round
Add up all the turns the turtle makes in going once round the square, triangle or hexagon, and you get 360° every time: one full turn. Seymour Papert and his colleagues called this the Total Turtle Trip Theorem: a turtle that walks round the edge of a shape and comes back facing the same way has turned through a whole number of full turns — exactly one if the path never crosses itself. The five-pointed star crosses itself, and its turtle turns twice round, 720°. This is a first glimpse of ideas in geometry and topology about how much a path winds.
Wonder Trails
Optional, and never graded: a question that leads somewhere further.
Wonder Trail · Optional · never gradedCan a computer decide?Some programs stop and some loop forever. Could someone write one clever program that looks at any program, together with its input, and always correctly says whether it will stop?Follow the trailHistory and global context
- Written methods. Around 820 CE, in Baghdad, Muḥammad ibn Mūsā al-Khwārizmī explained how to calculate with the Hindu–Arabic numerals, place value and all. His name, written Algoritmi in Latin, gave us the word algorithm.
- Carrying on a counting board. On an abacus — the Chinese suanpan, the Japanese soroban, the Russian schoty — a carry happens when a rod fills up: you clear it and move one bead on the next rod.
- Euclid's loop. About 300 BCE, Euclid's Elements described a method for finding the greatest common divisor of two numbers by repeatedly subtracting (or dividing with remainder) until nothing is left — a "repeat until" loop that always stops.
- A loom that loops. In 1804 Joseph-Marie Jacquard in France built a loom controlled by a chain of punched cards; joining the chain into a loop repeats a woven pattern.
- The first loops in a program. In her notes of 1843 on Charles Babbage's planned Analytical Engine, Ada Lovelace described how a group of operations could be repeated — a "cycle" — many times.
- Will it stop? In 1936 Alan Turing in England proved that no algorithm can decide, for every program, whether it will ever stop.
- Turtles and blocks. In the late 1960s Seymour Papert, Cynthia Solomon and Wally Feurzeig created the Logo language, in which children write
REPEAT 4 [FORWARD 100 RIGHT 90]to draw a square. Since 2007, millions of children around the world have used repeat and if–then blocks in Scratch, made at the MIT Media Lab.
For grown-ups: further reading
- Tim Bell, Ian H. Witten and Mike Fellows, Computer Science Unplugged (1998; later editions) — classroom activities on algorithms, without computers.
- Seymour Papert, Mindstorms: Children, Computers, and Powerful Ideas (1980) — turtles, loops and how children learn by programming.
- Harold Abelson and Andrea diSessa, Turtle Geometry (1981) — the mathematics of turtle programs, including the Total Turtle Trip Theorem.
- Linda Liukas, Hello Ruby: Adventures in Coding (2015) — a picture book about loops, conditions and thinking like a programmer.