If you ever wondered how Credit Card Numbers, IMEI Numbers or Canadian Social¬†Insurance¬†Numbers are validated you can take a look at this Programming Praxis article . It’s all about a simple, tiny, patented (now public domain) algorithm invented by IBM’s computer scientist Hans Peter Luhn .

The validation is pretty simple, and works this way:

1. Given a number we will consider the last digit a check-digit .
2. Starting from the check digit backwards we will multiply by 2 every even digit .
3. We will sum all digits (both doubled and undoubled) .
4. If the sum is a multiple of 10 then the number is valid, else is invalid .

Example:

5 4 3 2 9 8 3 7 6
5 8 3 4 9 (1+6) 3 (1+4) 6 = 50 (which is a muliple of 10, thus the number is valid)

I’ve written the implementation of this simple algorithm using python 3.x . The solution can become rather elegant if we use the functional programming features that python offers us:

def luhn_check(num):
    ''' Number - List of reversed digits '''
    digits = [int(x) for x in reversed(str(num))]
    check_sum = sum(digits[::2]) + sum((dig//10 + dig%10) for dig in [2*el for el in digits[1::2]])
    return check_sum%10 == 0

if __name__ == "__main__":
    print(luhn_check(543298376))

And the output:

True

Observations:

  1. At line 3 we are using list comprehension to transform the number in a list of digits starting backwards (the check digit is at position 0) .
  2. We are using “//” operator for Floor division, as the “/” operator in the 3.x series means True division .
  3. (dig//10 + dig%10) this trick works well when we need determine the sum of the digits of a number smaller than 100 . Eg. (19//10 + 19%10) = (1 + 9) = 10 .

Leave a reply

required


6 × = twenty four

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>