A. Programming Concepts and Skills · Data Types, Files and ExpressionsAlgorithms Built on Remainders: Digits, Bases, GCD and Check Digits
A1.1 A4.3About 75 minutes
Learning goals- I can extract, count, sum and reverse the digits of an integer with
% and //. - I can convert an integer to any base from 2 to 16 by repeated division.
- I can trace and implement Euclid's algorithm for the greatest common divisor.
- I can explain and implement a check-digit algorithm such as Luhn.
Words to know
digit extraction
Getting digits from an integer: n % 10 is the last digit and n // 10 removes it.
base (radix)
How many different digits a number system uses: base 10 (decimal), base 2 (binary), base 16 (hexadecimal).
greatest common divisor (GCD)
The largest integer that divides two integers exactly. gcd(48, 180) = 12.
Euclid's algorithm
Find gcd(a, b) by repeatedly replacing (a, b) with (b, a % b) until b is 0.
check digit
An extra digit computed from the others so that typing mistakes can be detected.
Luhn algorithm
A mod-10 check-digit method used for payment card numbers and Canadian Social Insurance Numbers.
loop invariant
A statement that is true before and after every pass of a loop; used to reason about why an algorithm is correct.
Small operator, big algorithms
In the last lesson, // and % solved one-step problems. Now you will put them inside loops to build real algorithms: taking a number apart digit by digit, writing numbers in other bases, finding greatest common divisors, and catching typing mistakes in ID numbers.
These algorithms show up in first-year university computer science and in discrete mathematics courses. They are also short enough to trace by hand, which makes them favourite test questions.
Taking a number apart
For a non-negative integer n:
n % 10 is the last digit.n // 10 is the number with the last digit removed.
Repeat until n is 0 and you visit every digit, from right to left. This works in any base: n % 2 and n // 2 peel off binary digits (bits), and n % 16 and n // 16 peel off hexadecimal digits.
n % 10 is the last digit and n // 10 drops it. Repeat until the number is 0.def digit_sum(n):
"""Return the sum of the decimal digits of a non-negative int n."""
total = 0
while n > 0:
total += n % 10 # last digit
n //= 10 # drop it
return total
def reverse_digits(n):
"""Return n with its decimal digits reversed (n >= 0)."""
result = 0
while n > 0:
result = result * 10 + n % 10
n //= 10
return result
print(digit_sum(4071), reverse_digits(4071), reverse_digits(1200))
Two digit algorithms. Notice reverse_digits(1200) is 21: leading zeros vanish in an int. (If you need to keep them, work with a string.) Output: 12 1704 21
Why not just use a string?
str(n) and a loop over characters also works, and is often clearer. The arithmetic method matters when you must not convert (embedded systems, interview questions), when you need the digits as numbers right away, and because it shows exactly what the computer does. Note that both methods need care with negative numbers: use abs(n) first.
Converting to another base
To write n in base b, divide by b over and over. Each remainder is the next digit, starting from the rightmost. In ICS3U you converted to binary and hexadecimal by hand; now you automate it for any base.
DIGITS = "0123456789ABCDEF"
def to_base(n, base):
"""Return the string for non-negative int n in the given base (2 to 16)."""
if n == 0:
return "0"
out = ""
while n > 0:
n, r = divmod(n, base)
out = DIGITS[r] + out # put the new digit in front
return out
print(to_base(156, 2), to_base(156, 16), to_base(156, 8))
print(int("10011100", 2), int("9C", 16))
Repeated division converts to any base. int(text, base) goes the other way. Python's built-ins bin, hex and oct do the same job, but writing it yourself is a classic test question. Output, line by line: 10011100 9C 234 | 156 156
Euclid's algorithm for the GCD
The greatest common divisor is needed to reduce fractions, to find when two repeating events line up again, and in cryptography (a possible topic in the sibling unit Topics in Computer Science). Euclid's idea: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
def gcd(a, b):
"""Greatest common divisor by Euclid's algorithm (a, b >= 0, not both 0)."""
while b != 0:
a, b = b, a % b
return a
print(gcd(1071, 462))
print(gcd(48, 180), gcd(17, 5))
Euclid's algorithm is over 2000 years old and still one of the fastest ways to find a GCD. Each step replaces the pair (a, b) by (b, a % b). Output, line by line: 21 | 12 1
Worked exampleExample 1: Trace Euclid's algorithm
Trace gcd(1071, 462) and explain why it works.
- Pair (1071, 462):
1071 % 462 is 147 (462 × 2 = 924, 1071 − 924 = 147). New pair (462, 147). - Pair (462, 147):
462 % 147 is 21 (147 × 3 = 441). New pair (147, 21). - Pair (147, 21):
147 % 21 is 0 (21 × 7 = 147). New pair (21, 0). Since b is 0, return a = 21. - Why it works: any number that divides both a and b also divides a − kb, which includes a % b. So (a, b) and (b, a % b) have exactly the same common divisors. The numbers shrink every step, so the loop must end, and gcd(a, 0) is a.
- Efficiency: the remainders shrink fast (roughly at least halving every two steps), so even 100-digit numbers need only a few hundred steps. Compare that with trying every possible divisor.
gcd(1071, 462) = 21, found in 3 remainder steps.
Check digits: catching typing mistakes
When a person types a long number, mistakes happen: one wrong digit, or two neighbouring digits swapped. A check digit is an extra digit calculated from the others. If the number is mistyped, the check usually fails, and the program can ask the user to re-enter it before anything goes wrong.
The Luhn algorithm (also called mod 10) is used for payment card numbers and Canadian Social Insurance Numbers:
- Starting from the rightmost digit (the check digit) and moving left, double every second digit.
- If doubling gives a two-digit number, subtract 9 (the same as adding its two digits).
- Add everything up. The number is valid if the total
% 10 == 0.
def luhn_valid(number):
"""Return True if the digit string passes the Luhn (mod 10) check."""
total = 0
for i, ch in enumerate(reversed(number)):
d = int(ch)
if i % 2 == 1: # every second digit from the right
d *= 2
if d > 9:
d -= 9
total += d
return total % 10 == 0
print(luhn_valid("79927398713"))
print(luhn_valid("79927398710"))
print(luhn_valid("79927398731")) # two digits swapped
The Luhn check catches every single wrong digit and most swaps of two neighbouring digits. Output, line by line: True | False | False
Worked exampleExample 2: Designing a check digit
A school library gives each book a 5-digit ID and adds a 6th check digit so that the sum of all six digits is a multiple of 10. Write the expression for the check digit of ID 40718, and decide whether this simple scheme catches a swap of two neighbouring digits.
- The five digits sum to 4 + 0 + 7 + 1 + 8 = 20.
- The check digit c must make (20 + c) % 10 == 0. In general
c = (10 - total % 10) % 10. The outer % 10 turns a 10 into 0 when the total is already a multiple of 10. - Here
(10 - 20 % 10) % 10 = (10 - 0) % 10 = 0, so the full ID is 407180. - A swap such as 40718 → 47018 keeps the same digits, so the same sum: the error is not caught. That is why real schemes (Luhn, ISBN) give digits different weights depending on their position.
Check digit 0. A plain digit sum catches any single wrong digit but no swaps; position weights fix that.
Just for funA funny-but-true fact: Euclid described his GCD method in Elements more than 2000 years ago, which makes it one of the oldest algorithms still in daily use. Its extended version is still used in the cryptography that protects web connections.
Hands-on activityCheck-digit hunt
You need: Python, a pencil, and a few product barcodes (UPC codes) from boxes and cans in your kitchen. (Do not use real payment cards or SIN cards: practise only with the test number in this lesson and with grocery barcodes.)
- A 12-digit UPC-A barcode uses this rule: multiply the digits in odd positions (1st, 3rd, …, 11th, counting from the left) by 3, add the digits in even positions (2nd to 10th), and the 12th digit is the check digit
c that makes the total plus c a multiple of 10. - Write
upc_check(first11) that returns the check digit, using (10 - total % 10) % 10. - Test it on at least four barcodes from your kitchen. Every one should match the 12th printed digit.
- Change one digit of a real barcode and show that your function now disagrees with the printed check digit.
What to look for: the weights 3, 1, 3, 1, … applied from the left, the outer % 10, and a correct match on real barcodes.
Your turn
1Trace digit_sum(9405): list the values of total and n after each pass.
Pass 1: total 5, n 940. Pass 2: total 5, n 94. Pass 3: total 9, n 9. Pass 4: total 18, n 0. Returns 18.
2What does reverse_digits(530) return? Why?
35. The first digit peeled off is 0, so result starts as 0, then 3, then 35. The leading zero of "035" disappears in an int.
3Use repeated division to convert 45 to binary. Show the remainders.
45 → 22 r1, 22 → 11 r0, 11 → 5 r1, 5 → 2 r1, 2 → 1 r0, 1 → 0 r1. Bottom up: 101101.
4What does to_base(255, 16) return?
"FF": 255 → 15 r15 (F), 15 → 0 r15 (F).
(84, 36) → (36, 12) → (12, 0). Answer 12.
6Check whether 4539 1488 0343 6467 passes Luhn. (Use the program, or by hand.)
Running luhn_valid("4539148803436467") gives True: the doubled-and-adjusted digits total 80, a multiple of 10.
7A 5-digit ID has digits summing to 23. Using the scheme in Example 2, what is the check digit?
(10 - 23 % 10) % 10 = (10 − 3) % 10 = 7. Then 23 + 7 = 30.
More practice: warm-up
1What is the last digit of 8126, as a Python expression?
110 (6 → 3 r0, 3 → 1 r1, 1 → 0 r1).
5In the Luhn check, the number is valid when the total is a multiple of what?
More practice: on your own
1Write count_digits(n) that returns how many digits a positive int has, using only //.
count = 0 then while n > 0: n //= 10; count += 1 (each on its own line) and return count. For 4071 it returns 4. (For n = 0 you would need a special case returning 1.)
2Why does to_base put each new digit in front of out rather than at the end?
The remainders come out from the least significant digit first. Adding each one in front puts the first remainder at the right-hand end, where it belongs.
3Use gcd to reduce the fraction 462/1071 to lowest terms.
gcd(1071, 462) = 21. 462 / 21 = 22 and 1071 / 21 = 51, so the fraction is 22/51.
4A city bus leaves every 12 minutes and a train every 18 minutes. They both leave at 8:00. When do they next leave together? Use gcd.
lcm(12, 18) = 12 × 18 / gcd(12, 18) = 216 / 6 = 36 minutes, so at 8:36. (Use a * b // gcd(a, b).)
5Explain why doubling a digit and subtracting 9 when the result is over 9 is the same as adding the two digits of the result.
A doubled digit is between 10 and 18. Its digits are 1 and (result − 10), which add up to result − 9.
Challenge
1Show that Luhn catches every single-digit error. Hint: think about a digit that is not doubled and one that is.
If an undoubled digit d changes to e, the total changes by e − d, which is between −9 and 9 and not 0, so the total is no longer a multiple of 10. For a doubled position, the values 0–9 map to 0, 2, 4, 6, 8, 1, 3, 5, 7, 9: ten different values, so changing the digit changes its contribution by a nonzero amount less than 10 in size. Either way the total stops being a multiple of 10.
2Find a swap of two neighbouring digits that Luhn does not catch.
Swapping 0 and 9 ("09" ↔ "90"). Whichever digit is doubled: 0 → 0 and 9 → 18 − 9 = 9, so the pair always contributes 0 + 9 = 9 in either order. The total does not change, so the error is missed.
3Write a recursive version of gcd and explain why it always stops for non-negative inputs.
def gcd(a, b): then return a if b == 0 else gcd(b, a % b). Each call replaces b by a % b, which is strictly smaller than b (since 0 ≤ a % b < b), so b reaches 0 after finitely many calls. Recursion is studied in depth in the sibling unit Algorithm Design and Analysis.
Quiz
1. What does this loop compute for a positive int n?
c = 0while n > 0: n //= 10 c += 1
2. What is 29 written in binary?
3. In Euclid's algorithm, what pair comes after (60, 22)?
5. Why do serious check-digit schemes weight digits differently by position?
6. Which expression gives the check digit c that makes (total + c) % 10 == 0?
Big idea: this lesson applies A1.1 (integer division and remainders) inside loops. The functions are documented with docstrings, practising A4.3.
How to help: the barcode activity is safe and satisfying. Please make sure your teen does not test with real payment card or SIN numbers; the test number 79927398713 is a standard example, not a real account.
Common difficulties:
- Reading binary remainders top to bottom instead of bottom to top.
- Forgetting that leading zeros vanish when digits are stored in an
int. - In Euclid's algorithm, writing
a, b = a % b, b (wrong order). - In Luhn, doubling the wrong digits: start counting from the right, and the check digit itself is not doubled.