Identification numbers are everywhere: grocery items, driver's licence, credit cards, ISBN's, money orders, bank accounts, library, UPS packages, books, etc. Quick methods for checking whether an identification number is "valid" are important for detecting scanning errors, and human transcription errors.
Below we briefly discuss three types of identification numbers: UPC, ISBN, and credit cards, and the mathematics behind checking them for validity.
UPC codes are the bar codes found on all items sold in stores.
code: $\overrightarrow{b} = (b_1,b_2,b_3, \ldots, b_{12})$
weight: $\overrightarrow{w} = (3,1,3,1,3,1,3,1,3,1,3,1)$
condition for a valid UPC code: $$ \overrightarrow{b}\cdot \overrightarrow{w} \equiv 0 \text{ (mod } 10) $$
b=vector(ZZ,[0,1,2,3,4,5,6,7,8,9,0,5])
w=vector(ZZ,[3,1,3,1,3,1,3,1,3,1,3,1])
b.dot_product(w)%10
0
(replaced with ISBN 13 after January 2007)
code: $\overrightarrow{b} = (b_1,b_2,b_3, \ldots, b_{10})$
weight: $\overrightarrow{w} = (10,9,8,7,6,5,4,3,2,1)$
condition for a valid UPC code: $$ \overrightarrow{b}\cdot \overrightarrow{w} \equiv 0 \text{ (mod } 11) $$
b=vector(ZZ,[8,1,7,5,2,5,7,6,6,0])
w=vector(ZZ,[10,9,8,7,6,5,4,3,2,1])
b.dot_product(w)%11
0
(replaced ISBN 10 after January 2007)
ISBN-10-code.png
code: $\overrightarrow{b} = (b_1,b_2,b_3, \ldots, b_{13})$
weight: $\overrightarrow{w} = (1,3,1,3,1,3,1,3,1,3,1,3,1)$
condition for a valid UPC code: $$ \overrightarrow{b}\cdot \overrightarrow{w} \equiv 0 \text{ (mod } 10) $$
b=vector(ZZ,[9,7,8,2,8,9,6,4,5,0,1,8,3])
w=vector(ZZ,[1,3,1,3,1,3,1,3,1,3,1,3,1])
b.dot_product(w)%10
0
b=vector(ZZ,[9,7,8,8,1,7,5,2,5,7,6,6,5])
w=vector(ZZ,[1,3,1,3,1,3,1,3,1,3,1,3,1])
b.dot_product(w)%10
0
The Luhn algorithm was developed by German computer scientist Hans Peter Luhn in 1954. It is a simple checksum formula used to validate identification numbers such as credit card numbers. The algorithm was designed to protect against accidental errors, such as a digit mistyping. It is used in the situation when a user has keyed in a credit card number (or scanned it) and wants to validate it before sending it our for debit authorization.
notes about python code below:
num = [int(x) for x in str(cc)] -> converts credit card number to a list of digits.
num[-2::-2] -> is the list of numbers which will be doubled (start at index -2 and pick every second one).
divmod(d*2, 10) -> (quotient, remainder) -> this allows us to sum digits of each two digit numbers.
def is_luhn_valid(cc):
num = [int(x) for x in str(cc)]
return sum(num[::-2] + [sum(divmod(d * 2, 10)) for d in num[-2::-2]]) % 10 == 0
Example: Is the number on this card valid? 4552720412345678
is_luhn_valid(4552720412345678)
False
For the card above, the last digit "8" can be changed to another digit so that the resulting card is valid. What should the last digit be changed to?
Example: Is the number on this card valid? 4417123456789113
is_luhn_valid(4417123456789113)
True