Luhn Algorithm - Informal Explanation

Informal Explanation

The formula verifies a number against its included check digit, which is usually appended to a partial account number to generate the full account number. This account number must pass the following test:

  1. Counting from the check digit, which is the rightmost, and moving left, double the value of every second digit.
  2. Sum the digits of the products (e.g., 10: 1 + 0 = 1, 14: 1 + 4 = 5) together with the undoubled digits from the original number.
  3. If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.

Assume an example of an account number "7992739871" that will have a check digit added, making it of the form 7992739871x:

Account number 7 9 9 2 7 3 9 8 7 1 x
Double every other 7 18 9 4 7 6 9 16 7 2 x
Sum of digits 7 9 9 4 7 6 9 7 7 2 =67

The check digit (x) is obtained by computing the sum of digits then computing 9 times that value modulo 10 (in equation form, (67 * 9 mod 10)). In algorithm form:

  1. Compute the sum of the digits (67).
  2. Multiply by 9 (603).
  3. The last digit, 3, is the check digit.

(Alternate method) The check digit (x) is obtained by computing the sum of digits then subtracting the units digit from 10 (67 = Units digit 7; 10 - 7 = check digit 3). In algorithm form:

  1. Compute the sum of the digits (67).
  2. Take the units digit 7.
  3. Subtract the units digit from 10.
  4. The result, 3, is the check digit.

This, makes the full account number read 79927398713.

Each of the numbers 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 can be validated as follows.

  1. Double every second digit, from the rightmost: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
  2. Sum all the individual digits (digits in parentheses are the products from Step 1): x (the check digit) + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 7 = x + 67.
  3. If the sum is a multiple of 10, the account number is possibly valid. Note that 3 is the only valid digit that produces a sum (70) that is a multiple of 10.
  4. Thus these account numbers are all invalid except possibly 79927398713 which has the correct checkdigit.

Read more about this topic:  Luhn Algorithm

Famous quotes containing the words informal and/or explanation:

    “We as a nation need to be reeducated about the necessary and sufficient conditions for making human beings human. We need to be reeducated not as parents—but as workers, neighbors, and friends; and as members of the organizations, committees, boards—and, especially, the informal networks that control our social institutions and thereby determine the conditions of life for our families and their children.”
    —Urie Bronfenbrenner (b. 1917)

    “Auden, MacNeice, Day Lewis, I have read them all,
    Hoping against hope to hear the authentic call . . .
    And know the explanation I must pass is this
    MYou cannot light a match on a crumbling wall.”
    —Hugh MacDiarmid (1892–1978)