Generating Luhn Checksums

Question

There are lots of implementations for validating Luhn checksums but very few for generating them. I've come across this one however in my tests it has revealed to be buggy and I don't understand the logic behind the delta variable.

I've made this function that supposedly should generated Luhn checksums but for some reason that I haven't yet understood the generated checksums are invalid half of the time.

function Luhn($number, $iterations = 1)
{
    while ($iterations-- >= 1)
    {
        $stack = 0;
        $parity = strlen($number) % 2;
        $number = str_split($number, 1);

        foreach ($number as $key => $value)
        {
            if ($key % 2 == $parity)
            {
                $value *= 2;

                if ($value > 9)
                {
                    $value -= 9;
                }
            }

            $stack += $value;
        }

        $stack = 10 - $stack % 10;

        if ($stack == 10)
        {
            $stack = 0;
        }

        $number[] = $stack;
    }

    return implode('', $number);
}

Some examples:

Luhn(3); // 37, invalid
Luhn(37); // 372, valid
Luhn(372); // 3728, invalid
Luhn(3728); // 37283, valid
Luhn(37283); // 372837, invalid
Luhn(372837); // 3728375, valid

I'm validating the generated checksums against this page, what am I doing wrong here?

---

For future reference, here is the working function.

function Luhn($number, $iterations = 1)
{
    while ($iterations-- >= 1)
    {
        $stack = 0;
        $number = str_split(strrev($number), 1);

        foreach ($number as $key => $value)
        {
            if ($key % 2 == 0)
            {
                $value = array_sum(str_split($value * 2, 1));
            }

            $stack += $value;
        }

        $stack %= 10;

        if ($stack != 0)
        {
            $stack -= 10;
        }

        $number = implode('', array_reverse($number)) . abs($stack);
    }

    return $number;
}

I dropped the $parity variable since we don't need it for this purpose, and to verify:

function Luhn_Verify($number, $iterations = 1)
{
    $result = substr($number, 0, - $iterations);

    if (Luhn($result, $iterations) == $number)
    {
        return $result;
    }

    return false;
}

Answer 1

Edit: Sorry, I realize now that you had almost my entire answer already, you had just incorrectly determined which factor to use for which digit.

My entire answer now can be summed up with this single sentence:

You have the factor reversed, you're multiplying the wrong digits by 2 depending on the length of the number.

---

Take a look at the Wikipedia article on the Luhn algorithm.

The reason your checksum is invalid half the time is that with your checks, half the time your number has an odd number of digits, and then you double the wrong digit.

For 37283, when counting from the right, you get this sequence of numbers:

  3 * 1 =  3             3
  8 * 2 = 16 --> 1 + 6 = 7
  2 * 1 =  2             2
  7 * 2 = 14 --> 1 + 4 = 5
+ 3 * 1 =  3             3
=                       20

The algorithm requires you to sum the individual digits from the original number, and the individual digits of the product of those "every two digits from the right".

So from the right, you sum 3 + (1 + 6) + 2 + (1 + 4) + 3, which gives you 20.

If the number you end up with ends with a zero, which 20 does, the number is valid.

Now, your question hints at you wanting to know how to generate the checksum, well, that's easy, do the following:

1. Tack on an extra zero, so your number goes from xyxyxyxy to xyxyxyxy0
2. Calculate the luhn checksum sum for the new number
3. Take the sum, modulus 10, so you get a single digit from 0 to 10
4. If the digit is 0, then congratulations, your checksum digit was a zero
5. Otherwise, calculate 10-digit to get what you need for the last digit, instead of that zero

Example: Number is 12345

1. Tack on a zero: 123450

2. Calculate the luhn checksum for 123450, which results in

   0   5    4    3    2    1
   1   2    1    2    1    2  <-- factor
   0   10   4    6    2    2  <-- product
   0  1 0   4    6    2    2  <-- sum these to: 0+1+0+4+6+2+2=15
   

3. Take the sum (15), modulus 10, which gives you 5

4. Digit (5), is not zero
5. Calculate 10-5, which gives you 5, the last digit should be 5.

So the result is 123455.

Answer 2

your php is buggy, it leads into an infinite loop. This is the working version that I'm using, modified from your code

function Luhn($number) {

$stack = 0;
$number = str_split(strrev($number));

foreach ($number as $key => $value)
{
    if ($key % 2 == 0)
    {
        $value = array_sum(str_split($value * 2));
    }
    $stack += $value;
}
$stack %= 10;

if ($stack != 0)
{
    $stack -= 10;     $stack = abs($stack);
}


$number = implode('', array_reverse($number));
$number = $number . strval($stack);

return $number; 

}

Create a php and run in your localhost Luhn(xxxxxxxx) to confirm.