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:
1 2 3 4 5 6 7 8 |
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:
1 |
True |
Observations:
- 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) .
- We are using “//” operator for Floor division, as the “/” operator in the 3.x series means True division .
- (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 .