Correct permutation cycle for Verhoeff algorithm

Question

Hello,

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.