RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a check-digit function and more number reversals. (Note that this is open until 14 August 2022.)

Task 1: Damm Algorithm

You are given a positive number, $n.

Write a script to validate the given number against the included check digit.

The Damm algorithm is really interesting: its actual procedure is simple, a digit-by-digit table lookup based on the previous intermediate result (or 0) and the present digit, but the cleverness is in the table, constructed such that any single-digit error or adjacent-digit transposition will change the result.

For language with sloppy string/number types this is nearly trivial, as here in Perl:

sub damm($n) {
  my @tab = (
    [0,3,1,7,5,9,8,6,4,2],
    [7,0,9,2,1,5,4,8,6,3],
    [4,2,0,6,8,7,1,3,5,9],
    [1,7,5,0,9,8,3,4,2,6],
    [6,1,2,3,0,4,5,9,7,8],
    [3,6,7,4,2,0,9,5,8,1],
    [5,8,6,9,7,2,0,1,3,4],
    [8,9,4,5,3,6,2,0,1,7],
    [9,4,3,8,6,1,7,2,0,5],
    [2,5,8,1,4,3,6,7,9,0],
      );
  my $c = 0;
  foreach my $digit (split '',$n) {
    $c = $tab[$c][$digit];
  }
  return $c;
}

sub checkdamm($n) {
  return (damm($n)==0)?1:0;
}

(I use two separate functions because, although checkdamm is the only one required, I can easily picture wanting to know the actual checksum too.)

Where types do exists, as in JavaScript, it gets a little more fiddly:

    for (let digit of n.toString().split("")) {
        c = tab[c][parseInt(digit)];
    }

I do rather like the PostScript though.

/damm {
    1 dict begin
    /tab [
        [0 3 1 7 5 9 8 6 4 2] 
        [7 0 9 2 1 5 4 8 6 3] 
        [4 2 0 6 8 7 1 3 5 9] 
        [1 7 5 0 9 8 3 4 2 6] 
        [6 1 2 3 0 4 5 9 7 8] 
        [3 6 7 4 2 0 9 5 8 1] 
        [5 8 6 9 7 2 0 1 3 4] 
        [8 9 4 5 3 6 2 0 1 7] 
        [9 4 3 8 6 1 7 2 0 5] 
        [2 5 8 1 4 3 6 7 9 0] 
    ] def
    [ exch
        {
            dup 0 gt {
                dup 10 mod exch
                10 idiv
            } {
                pop
                exit
            } ifelse
        } loop
    ] reverse 0 exch {
        tab 3 -1 roll get exch get
    } forall
    end
} bind def

Task 2: Palindromic Prime Cyclops Numbers

Write a script to generate first 20 Palindromic Prime Cyclops Numbers.

A cyclops number is a number with an odd number of digits that has a zero in the center only.

Sequence A136098 at the OEIS.

As I see it this is a filtering process. For each integer, starting at 1:

• check that it contains no zeroes
• turn it into a palindromic cyclops (i.e ABC → ABC0CBA, and increasing ABC always leads to increasing the palindrome)
• check that for primality (using code I've already written)

I could also reject candidates that started with 5 or an even number, since the cyclops will end with that and it won't be prime, but when I tried this it was slower than simply letting them fall into the primality test and be rejected there.

(Or I could turn the whole thing inside-out to generate a sequence of primes and test them for being palindromic cyclops numbers, but while I haven't checked I strongly suspect this would be less efficient.)

So in PostScript:

/ppc {
    4 dict begin
    /ct exch def
    [
        /fh 0 def
        {

Increment the candidate number.

            /fh fh 1 add def
            /q true def

Check for zeroes.

            fh {
                dup 0 gt {
                    dup 10 mod 0 eq
                    {
                        /q false def
                        pop
                        exit
                    } {
                        10 idiv
                    } ifelse
                } {
                    pop
                    exit
                } ifelse
            } loop

If no zeroes, duplicate (and because PostScript strings are always references, make a copy with dup length string cvs)

            q {
                [ fh cvss dup dup length string cvs reverse (0)
                  exch ] () strjoin cvi

And check for primality; if true, leave it on the stack, which is our output array.

                dup isprime {
                    /ct ct 1 sub def
                    ct 0 le {
                        exit
                    } if
                } {
                    pop
                } ifelse
            } if
            ct 0 le {
                exit
            } if
        } loop
    ]
    end
} bind def

More conventionally in Kotlin:

fun ppc(ct: Int): List<Int> {
    var o = ArrayList<Int>()
    var fh = 0
    while (o.size < ct) {
        fh += 1
        var t = fh
        var q = false
        while (t > 0) {
            if (t % 10 == 0) {
                q = true
                break
            }
            t /= 10
        }
        if (q) {
            continue
        }
        val sfh = fh.toString()
        val c = (sfh + "0" + sfh.reversed()).toInt()
        if (isprime(c.toLong())) {
            o.add(c)
        }
    }
    return o
}

Full code on github.