Correct permutation cycle for Verhoeff algorithm

Question

I'm implementing the Verhoeff algorithm for a check digit scheme, but there seems to be some disagreement in web sources as to which permutation cycle should form the basis of the permutation table.

Wikipedia uses: (36)(01589427)

while apparently, Numerical Recipies uses a different cycle and this book uses: (0)(14)(23)(56789), quoted from a 1990 article by Winters. It also notes that Verhoeff used the one Wikipedia quotes.

Now, my number theory is a little rusty, but the Wikipedia cycle clearly will repeat after the 8th power, while the book one will take 10, despite it saying that s^8=s. Table 2.14(b) has other errors in the 2-cycles, so this is dubious anyway.

Unfortunately, I don't have copies of the original articles (and am too tight to pay/disgusted that 40-year old knowledge is still being held to ransom by publishers), nor a copy of Numerical Recipes to check (and am loath to install their paranoia-induced copy protection plug-in to view online).

So does any one know which is correct? Are they both correct?

Answer 1

There's an old edition of Numerical Recipes available here as PDFs. Verhoeff algorithm is described in section 20.3. It uses the same permutation as the Wikipedia article.

Answer 2

The permutation (0)(14)(23)(56789) is better than the permutation (36)(01589427). This is because, (36)(01589427) can only detect 88.89% of the single transposition errors while (0)(14)(23)(56789) can detect all of them. Consider the numeric code 716 be given 0 as the check digit if (36)(01589427) is used. i.e., the code will be 7160. But, if the digits 1 and 6 are transposed, this check digit scheme does not give an error as the check sum is zero. This is not the case with (0)(14)(23)(56789).