Damm and Cyclops

Damm algorithm

Take care to spell that correctly.

The Damm algorithm takes a sequence of n digits and results in a check digit, m. If the check digit is appended to the original sequence, applying the Damm algorithm to the new sequence of n+1 digits results in a check digit of 0.

The algorithm uses a weakly totally anti-symmetric quasigroup of order 10. I'm sure we're all familiar with those, but in case we don't have one to hand, Wikipedia has kindly purloined one from Dr Damm's PhD thesis, and luckily Mohammad has used that one for his example.

Armed with the quasigroup and holding it in Perl's simulation of a two-dimensional array, the algorithm is very simple: start with an 'interim digit' of 0 and then replace the interim digit with the value in the 2D array at [$interim_digit, $digit] where $digit is successive digits of the supplied number.

We are given a number to test which already has the check digit appended, so if the final value of $interim_digit is zero, the check digit is correct - ie the original digit sequence is valid.  

We can check our working by taking a long string of digits, adding its check digit, and then verifying that swapping two digits or altering a single digit results in a non-zero result from the algorithm.

Even in my rather verbose programming style that's only 5 lines of code (apart from initialising the table).

Palindromic prime cyclops numbers

The Damm algorithm is useful: it could be (but isn't) used for ISBNs or any long and easily mistyped string of digits.

Usefulness is not a feature - so far as I know - for palindromic prime cyclops numbers, which are prime numbers with an odd count of digits with the only zero as the middle digit.

My first thought was to start at 100 and check every number for being a PPCN. This works, but isn't very efficient. My second thought was only to check numbers with an odd number of digits - so 100 to 999 and then 10000 to 99999 and so on. That was a little quicker.

However, my third and submitted algorithm looks like this:

Loop $j up from 1 to something huge.  $j is going to be just the digits to the left of the central zero. 

First we discard any $j that contains a zero. 

Now we create a candidate number which is the concatenation of $j, '0' and $j reversed. So that is palindromic and has a single 0 in the right place, and all that remains is to check that it's prime. I used Math::Prime::Util to do that rather than write yet another sieve of Eratosthenes.

So far as I know, Perl has no intrinsic function to reverse a string, but this works:

join('', reverse(split('', $j)))

- that is, split the digits of the number into an array, reverse the array, and then join them together again.  There may be faster methods, but using my (third) algorithm generates PPCNs up into the millions without noticeable delay.