# Perl Weekly Challenge 177.

My solutions (task 1 and task 2 ) to the The Weekly Challenge - 177.

``````Submitted by: Mohammad S Anwar
You are given a positive number, \$n.

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

Example 1
Input: \$n = 5724
Output: 1 as it is valid number
Example 2
Input: \$n = 5727
Output: 0 as it is invalid number
``````

The Damm algorithm is useful for detecting changes in a single symbol within a sequence, as well as a single transposition between adjacent symbols. It is based on a weak totally anti-symmetric group consisting of an operation ∗ on the possible elements of the sequence, meaning, it obeys (c∗x)∗y=(c∗y)∗x⇒x=y for all elements c, x, y. The group is characterized by a table. Constructing the table is a more challenging task than using it. The Wikipedia article contains a sample table for the digits 0..9, namely

``````∗ 0 1 2 3 4 5 6 7 8 9
0 0 3 1 7 5 9 8 6 4 2
1 7 0 9 2 1 5 4 8 6 3
2 4 2 0 6 8 7 1 3 5 9
3 1 7 5 0 9 8 3 4 2 6
4 6 1 2 3 0 4 5 9 7 8
5 3 6 7 4 2 0 9 5 8 1
6 5 8 6 9 7 2 0 1 3 4
7 8 9 4 5 3 6 2 0 1 7
8 9 4 3 8 6 1 7 2 0 5
9 2 5 8 1 4 3 6 7 9 0
``````

Using the table is quite simple. To test the sequence N0N1N2…Nm, where the last digit is the check digit I evaluate (…((0∗N0)∗N1)…)∗Nm If the result is 0, then there are no simple errors as described above. This yields a simple 3-liner.

``````perl -MList::Util=reduce -E 'my @d= split "", "03175986427092154863420687135917509834266123045978"
."36742095815869720134894536201794386172052581436790";	my \$t=[map {[@d[10*\$_..10*\$_+9]]}(0..9)];
say "\$_->", (reduce {\$t->[\$a][\$b]} (0,split "", \$_))?0:1 for @ARGV;
' 5724 5727
``````

Results:

``````5724->1
5727->0
``````

The reason this works is that after a mistaken digit, say, replacing Nk by a different digit Mk, the subsequent partial sequences (…((0∗N0)∗N1)…)∗Mk)∗Nk+1)…)∗Nk+j do not coincide, for any j, with the original value (…((0∗N0)∗N1)…)∗Nk∗Nk+1)…)∗Nk+j, i.e., a change of one digit produces a change in a partial product that is not corrected by subsequent partial products. Similarly, a transposition produces a change in the partial product (…((0∗N0)∗N1)…)∗Nk+1)∗Nk) that is not corrected by subsequent partial products (…((0∗N0)∗N1)…)∗Nk+1)∗Nk)*Nk+2…)∗Nk+j. Choosing the multiplication table with zeroes in the diagonal, i.e., x∗x=0, allows us to choose the check digit as the product of all previous digits.

The full code is

`````` 1  # Perl weekly challenge 177
2  # Task 1: Damm algorithm
3  #
5  use v5.36;
6  use List::Util qw(reduce);
7  die "Usage: \$0 N1 [N2... ]\nTo check N_{i} with Damm's algorithm\n" unless @ARGV;
8  my @digits= map {split "", \$_} # consecutive digits of a Damm table
9      qw(0317598642 7092154863 4206871359 1750983426 6123045978
10         3674209581 5869720134 8945362017 9438617205 2581436790);
11  # Organice the digits as a 2D array
12  my \$table=[map {[@digits[10*\$_..10*\$_+9]]}(0..9)];
13  # The group operation \$n ∗ \$m is given by \$table->[\$n][\$m]
14  say "\$_ ", (reduce {\$table->[\$a][\$b]} (0,split "", \$_))?"isn't":"is", " correct"  for @ARGV;
``````

Example:

``````./ch-1.pl 5724 5727
``````

Results:

``````5724 is correct
5727 isn't correct
``````

# Task 2: Palindromic Prime Cyclops

``````Submitted by: Mohammad S Anwar

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.

Output
101, 16061, 31013, 35053, 38083, 73037, 74047, 91019, 94049,
1120211, 1150511, 1160611, 1180811, 1190911, 1250521, 1280821,
1360631, 1390931, 1490941, 1520251
``````

A solution may be obtained by generating numbers in sequence, skipping those that contain zeroes, reversing them to construct a cyclops number and testing it for primality. This fits into a oneliner.

``````perl -MMath::Prime::Util=is_prime -d -E '
\$i=1; while(\$n<20){\$c=\$i."0".reverse \$i; ++\$n, print "\$c " if \$i!~/0/ && is_prime(\$c); ++\$i}
'|fmt
``````

Results:

``````101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511
1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
``````

The full code is

``````# Perl weekly challenge 177
# Task 2: Palyndromic prime cyclops
#
use v5.36;
use Math::Prime::Util qw(is_prime);
my \$left=1;
my \$count=0;
my \$how_many=shift//20;
while(\$count<\$how_many){
my \$candidate=\$left."0".reverse \$left;
++\$count, print "\$candidate " if \$left!~/0/ && is_prime(\$candidate);
++\$left
}

./ch-2.pl 20|fmt
``````

Results:

``````101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511
1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
``````

# Other languages

I translate my solutions to other languages with which I’m not yet too familiar, to start learning about them. Surely, my solutions will not be the most elegant or efficient.

## Raku

``````1  # Perl weekly challenge 177
2  # Task 1: Damm algorithm
3  #
5  die "Usage: \$*PROGRAM-NAME N1 [N2... ]\nTo check Ni with Damm's algorithm\n" unless @*ARGS.Bool;
6  my @table= <0317598642 7092154863 4206871359 1750983426 6123045978 3674209581
7              5869720134 8945362017 9438617205 2581436790>.map({.comb.map({.Int})});
8  @*ARGS.map({say "\$^x ", (unshift(\$^x.comb.Array,0).reduce({@table[\$^a][\$^b]}))==0??
9           "is"!!"isn't", " correct"});
``````

Example:

``````./ch-1.raku 5724 5727
``````

Results:

``````5724 is correct
5727 isn't correct
``````

``````# Perl weekly challenge 177
# Task 2: Palyndromic prime cyclops
#
my \$left=1;
my \$count=0;
my \$how_many=@*ARGS[0]//20;
while \$count < \$how_many {
my \$candidate=\$left~0~\$left.flip;
if !(\$left ~~ /0/) && is-prime(\$candidate) {
++\$count;
"\$candidate ".print;
}
++\$left;
}
"".say;
``````

Example:

``````./ch-2.raku |fmt
``````

Results:

``````101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511
1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
``````

## Julia

`````` 1  # Perl weekly challenge 177
2  # Task 1: Damm algorithm
3  #
5  using PartialFunctions
6  table=[[0,3,1,7,5,9,8,6,4,2], [7,0,9,2,1,5,4,8,6,3],
7         [4,2,0,6,8,7,1,3,5,9], [1,7,5,0,9,8,3,4,2,6],
8         [6,1,2,3,0,4,5,9,7,8], [3,6,7,4,2,0,9,5,8,1],
9         [5,8,6,9,7,2,0,1,3,4], [8,9,4,5,3,6,2,0,1,7],
10         [9,4,3,8,6,1,7,2,0,5], [2,5,8,1,4,3,6,7,9,0]];
11  function checkdamm(n)
12      reduce((i,j)->table[i+1][j+1], vcat([0], map(parse \$ Int64, split(n, ""))))==0
13  end
14  if isempty(ARGS)
15      println("Usage: \$PROGRAM_FILE N1 [N2...]\nTo check N1 N2 for Damm correctness")
16      exit()
17  end
18  for n in ARGS
19      println(n , checkdamm(n) ? " is " : " isn't ", "correct")
20  end
``````

Example:

``````./ch-1.jl 5724 5727
``````

Results:

``````5724 is correct
5727 isn't correct
``````

Here is a version in Julia:

``````# Perl weekly challenge 177
# Task 2: Palyndromic prime cyclops
#
using Primes
let left=1
count=0
howmany=if isempty(ARGS) 20 else parse(Int64,ARGS[1]) end
while(count<howmany)
leftstring=string(left)
if !occursin("0", leftstring)
candidate=parse(Int64, leftstring*"0"*reverse(leftstring))
if isprime(candidate)
count +=1
print("\$candidate ")
end
end
left += 1
end
end
``````

Example:

``````./ch-2.jl|fmt
``````

Results:

``````101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511
1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
``````

## Emacs-Lisp

`````` ;; Perl weekly challenge 177

(defun show-damm (n)
"Print if string of digits n is correct by applying Damm's algorithm"
(princ (format "%s %s correct " n (if (test-damm n) "is" "isn't"))))
(defun test-damm (n)
"Test string of digits n for Damm-correctness"
(equal 0(test-damm1 (cons 0 (mapcar 'string-to-number(split-string n "" t))))))
(defun test-damm1 (s)
"Test the sequence of digits s for Damm-correctness"
(cl-reduce (lambda (i j)(aref2 table i j)) s))
(defun aref2 (table i j)
"Access 2D table with two indices"
(aref (aref table i) j))
(let
(
(table				; Damm table
(vconcat
(mapcar
(lambda(x)
(vconcat
(mapcar 'string-to-number (split-string x "" t))))
'("0317598642" "7092154863" "4206871359" "1750983426" "6123045978"
"3674209581" "5869720134" "8945362017" "9438617205" "2581436790"))))
(candidates '("5724" "5727")))	; examples to test
(mapc 'show-damm candidates))
``````

Results:

``````"5724 is correct 5727 isn't correct "
``````

`````` ;; Perl weekly challenge 177
;; Task 2: Palyndromic prime cyclops

(defun cyclops (how-many)
(cl-loop
for left from 1 				; danger: no guard
for left-string = (number-to-string left)
for has0 = (string-match "0" left-string)
for candidate = (string-to-number(concat left-string "0" (reverse left-string)))
for prime = (car (math-prime-test candidate 1))
for success = (and (not has0) prime)
for count = 0 then (if success (+ count 1) count)
while (< count how-many)
if success
collect candidate ))
(princ (cyclops 20))
``````

Results:

``````(101 16061 31013 35053 38083 73037 74047 91019 94049 1120211
1150511 1160611 1180811 1190911 1250521 1280821 1360631
1390931 1490941 1520251)
``````

I made also a version without the sophisticated common-lisp loop:

`````` ;; Perl weekly challenge 177
;; Task 2: Palyndromic prime cyclops

(defun cyclops (how-many)
(let ((left 1)(count 0)(result nil))
(while (< count how-many)
(let ((left-string (number-to-string left)))
(unless (string-match "0" left-string)
(let ((cyclops (string-to-number(concat left-string "0" (reverse left-string)))))
(when (car (math-prime-test cyclops 1))
(setq result (cons cyclops result))
(setq count (+ count 1))))))
(setq left (+ left 1)))
(reverse result)))
(print (cyclops 20))
``````

Results:

``````(101 16061 31013 35053 38083 73037 74047 91019 94049 1120211
1150511 1160611 1180811 1190911 1250521 1280821 1360631
1390931 1490941 1520251)
``````

I’m not sure which version reads better.

Written on August 8, 2022