{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Identification Numbers #\n", "\n", "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.\n", "\n", "Below we briefly discuss three types of identification numbers: UPC, ISBN, and credit cards, and the mathematics behind checking them for validity." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "### Universal Product Code (UPC) ###\n", "\n", "UPC codes are the bar codes found on all items sold in stores.\n", "\n", "\n", "\n", "code: $\\overrightarrow{b} = (b_1,b_2,b_3, \\ldots, b_{12})$\n", "\n", "weight: $\\overrightarrow{w} = (3,1,3,1,3,1,3,1,3,1,3,1)$\n", "\n", "condition for a valid UPC code:\n", "$$ \\overrightarrow{b}\\cdot \\overrightarrow{w} \\equiv 0 \\text{ (mod } 10) $$" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b=vector(ZZ,[0,1,2,3,4,5,6,7,8,9,0,5])\n", "w=vector(ZZ,[3,1,3,1,3,1,3,1,3,1,3,1])\n", "b.dot_product(w)%10" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### International Standard Book Number (ISBN-10)###\n", "\n", "(replaced with ISBN 13 after January 2007)\n", "\n", "\n", "\n", "code: $\\overrightarrow{b} = (b_1,b_2,b_3, \\ldots, b_{10})$\n", "\n", "weight: $\\overrightarrow{w} = (10,9,8,7,6,5,4,3,2,1)$\n", "\n", "condition for a valid UPC code:\n", "$$ \\overrightarrow{b}\\cdot \\overrightarrow{w} \\equiv 0 \\text{ (mod } 11) $$" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b=vector(ZZ,[8,1,7,5,2,5,7,6,6,0])\n", "w=vector(ZZ,[10,9,8,7,6,5,4,3,2,1])\n", "b.dot_product(w)%11" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### International Standard Book Number (ISBN-13)###\n", "\n", "(replaced ISBN 10 after January 2007)\n", "\n", "ISBN-10-code.png\n", "\n", "\n", "code: $\\overrightarrow{b} = (b_1,b_2,b_3, \\ldots, b_{13})$\n", "\n", "weight: $\\overrightarrow{w} = (1,3,1,3,1,3,1,3,1,3,1,3,1)$\n", "\n", "condition for a valid UPC code:\n", "$$ \\overrightarrow{b}\\cdot \\overrightarrow{w} \\equiv 0 \\text{ (mod } 10) $$" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b=vector(ZZ,[9,7,8,2,8,9,6,4,5,0,1,8,3])\n", "w=vector(ZZ,[1,3,1,3,1,3,1,3,1,3,1,3,1])\n", "b.dot_product(w)%10" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b=vector(ZZ,[9,7,8,8,1,7,5,2,5,7,6,6,5])\n", "w=vector(ZZ,[1,3,1,3,1,3,1,3,1,3,1,3,1])\n", "b.dot_product(w)%10" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Credit Card Validation:###\n", "\n", "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. \n", "\n", "\n", "\n", "\n", "\n", "\n", "notes about python code below:\n", "\n", " num = [int(x) for x in str(cc)] -> converts credit card number to a list of digits.\n", " \n", " num[-2::-2] -> is the list of numbers which will be doubled (start at index -2 and pick every second one).\n", " \n", " divmod(d*2, 10) -> (quotient, remainder) -> this allows us to sum digits of each two digit numbers." ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def is_luhn_valid(cc):\n", " num = [int(x) for x in str(cc)]\n", " return sum(num[::-2] + [sum(divmod(d * 2, 10)) for d in num[-2::-2]]) % 10 == 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Example:** Is the number on this card valid? 4552720412345678\n", "\n", "" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_luhn_valid(4552720412345678)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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? " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Example:** Is the number on this card valid? 4417123456789113\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_luhn_valid(4417123456789113)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 7.3", "language": "", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.10" } }, "nbformat": 4, "nbformat_minor": 1 }