## Perl Weekly Challenge 177: Damm Algorithm and Palindromic Prime Cyclops

These are some answers to the Week 177 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few of days from now (on Aug. 14, 2022 at 23:59). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

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 algorithm is a check digit algorithm named after H. Michael Damm, who presented it in 2004.

The process is quite simple. We’ll use the quasi-group table provided in the afore-mentioned Wikipedia article:

``````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
``````

### Damm Algorithm in Raku

The process is simple. We start with a temporary value of 0. For each digit in the input number, we look up the table with the temporary variable and the digit, and set the temporary variable to the integer found in the table. At the end, the number is valid is the temporary variable is 0. For our test, we will use the two examples provided in the task specification, and we will test all numbers in the `5700..5800` range.

``````my @damm =  < 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 >;

sub is-valid (\$n) {
my \$t = 0;
\$t = @damm[\$t][\$_] for \$n.comb;
return \$t == 0;
}

for 5724, 5727 -> \$test {
say \$test, is-valid(\$test) ?? " is valid." !! " is not valid.";
}
say "\nValid numbers between 5700 and 5800 are: ";
for 5700..5800 -> \$i {
print "\$i " if is-valid \$i;
}
say "";
``````

This program displays the following output:

``````\$ raku ./damm-algo.raku
5724 is valid.
5727 is not valid.

Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

### Damm Algorithm in Perl

The algorithm for finding the check digit is the same as the one for testing whether a number is valid. So, rather than simply testing the validity directly as we did in Raku, we’ll write a `find_check` subroutine to find the check digit. Then, a number will be valid if its check digit is 0. Thus, we sort of get the two functions for the price of one. Besides that, the process is essentially the same as in Raku. Check the Raku section above is you need further explanations.

``````use strict;
use warnings;
use feature qw/say/;

my @damm =  (
[ < 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 > ] );

sub find_check {
my \$n = shift;
my \$t = 0;
\$t = \$damm[\$t][\$_] for split //, \$n;
return \$t;
}

sub is_valid {
my \$n = shift;
return find_check(\$n) == 0;
}

for my \$test (5724, 5727) {
say \$test, is_valid(\$test) ? " is valid." : " is not valid.";
}
say "\nValid numbers between 5700 and 5800 are: ";
for my \$i (5700..5800) {
print "\$i " if is_valid \$i;
}
say "";
``````

This program displays the following output:

``````\$ perl  ./damm-algo.pl
5724 is valid.
5727 is not valid.

Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

### Damm Algorithm in Other Languages

We now present the same Damm algorithm in the following 18 guest languages (in alphabetic order):

• awk
• C
• D
• Dart
• Go
• Java
• JavaScript
• Julia
• Kotlin
• Lua
• Nim
• Pascal
• Python
• Ring
• Ruby
• Rust
• Scala
• Tcl

From now on, for all guest language implementations, the test will consist in listing the valid numbers between 5700 and 5800, a range that includes the two test cases (5724 and 5727) suggested in the task specification.

#### Damm Algorithm in awk

The awk programming language has minimal support for arrays. It doesn’t seem to support two-dimensional arrays, and iniitializing arrays in a pain in the neck (there may be some way, but the documentation is scarce). So we implement the `damm` lookup array as an array of strings and initialize it by initializing each item in the array (in the `populate_damm` function). Then we use the `substr` built-in function to retrieve the wanted value from the strings.

``````function is_valid(n) {
t = 0
for (j = 1; j <= length(n); j++) {
t = substr(damm[t],substr(n, j, 1) + 1 ,1)
}
return t == 0
}
function populate_damm() {
damm[0] = "0317598642"
damm[1] = "7092154863"
damm[2] = "4206871359"
damm[3] = "1750983426"
damm[4] = "6123045978"
damm[5] = "3674209581"
damm[6] = "5869720134"
damm[7] = "8945362017"
damm[8] = "9438617205"
damm[9] = "2581436790"
}
BEGIN {
populate_damm()
print("Valid numbers between 5700 and 5800 are: ")
for (i  = 5700; i<= 5800; i++) {
if (is_valid(i)) {
printf("%d ", i)
}
}
}
``````

Output:

``````\$ awk -f ./damm-algo.awk
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

Note that I was thinking about a bc implementation of the Damm algorithm, but I gave up the idea because the situation with arrays (and also documentation) is worse that in awk.

#### Damm Algorithm in C

Not much to say, the code is quite clear. Just note that, in the `temp = damm[temp][str[i] - '0'];` code line, we need to subtract the Ascii value of 0 (48) from the value in the `str` integer-to-string conversion in order to get proper subscripts. We will have to do the same in a number of other guest language implementations.

``````#include <stdio.h>

const char damm[10][10] = {
{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},
};

int is_valid(int num) {
int temp = 0;
char str[10];
int len = sprintf(str, "%d", num);   // convert input int to string
str[len] = '\0';
for (int i = 0; i < len; i++) {
temp = damm[temp][str[i] - '0'];
}
return temp == 0;
}

int main() {
printf("%s\n", "Valid numbers between 5700 and 5800 are: ");
for (int i = 5700; i < 5800; i++) {
if (is_valid(i))
printf("%d ", i);
}
printf("%s\n", "");
}
``````

Output:

``````\$ ./a.out
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in D

As usual, the D syntax is very similar to the C syntax, but D is just a bit simpler to use than C.

``````import std.stdio;
import std.conv;

auto damm = [
[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],
];

bool is_valid (int num) {
string str = to!string(num, 10);
int temp = 0;
foreach (ch; str) {
temp = damm[temp][ch - '0'];
}
return temp == 0;
}

void main() {
writeln("Valid numbers between 5700 and 5800 are: ");
for (int i = 5700; i < 5800; i++) {
if (is_valid(i))
printf("%d ", i);
}
writeln("");
}
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Dart

Like in awk, I haven’t found a good way to declare and initialize two-dimensional arrays in Dart, and the documentation is quite sparse. So I used the same solution as in awk: an array of strings.

``````import "dart:io";

var damm = [ "0317598642",
"7092154863",
"4206871359",
"1750983426",
"6123045978",
"3674209581",
"5869720134",
"8945362017",
"9438617205",
"2581436790" ];

void main() {
print("Valid numbers between 5700 and 5800 are:");
for (int i = 5700; i <= 5800; i++ ) {
if (is_valid(i)) {
stdout.write("\$i ");
}
}
stdout.write("\n");
}
bool is_valid(n) {
var digits = n.toString().split("");
int temp = 0;
var len = digits.length;
for (int i = 0; i < len; i++) {
var row = damm[temp];
var idx = int.parse(digits[i]);
temp = int.parse(row[idx]);
}
return temp == 0;
}
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Go

``````import (
"fmt"
"strconv"
)

var damm = [10][10] int {
{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},
}

func is_valid(num int) bool {
var n_str = strconv.Itoa(num)
var temp = 0
for _, ch := range n_str {
temp = damm[temp][ch-'0']
}
return temp == 0
}

func main() {
fmt.Println("Valid numbers between 5700 and 5800 are:")
for i := 5700; i <= 5800; i++ {
if is_valid(i) {
fmt.Printf("%d ", i)
}
}
fmt.Println("")
}
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Java

``````public class DammCheckDigit {
private static final int[][] damm =
{ {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} };

private static boolean is_valid(Integer num) {
char[] n = num.toString().toCharArray();
int temp = 0;
for (char ch : n) {
temp = damm[temp][ch - '0'];
}
return temp == 0;
}

public static void main(String[] args) {
System.out.printf("%s", "Valid numbers between 5700 and 5800 are:");
for(int i = 5700; i <= 5800; i++) {
if (is_valid(i))  System.out.printf("%d ", i);
}
System.out.printf("%s", "\n");
}
}
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in JavaScript

``````damm = [ [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] ];

function is_valid (n) {
let digits = n.toString().split("")
var temp = 0
for (var i = 0; i < digits.length; i++) {
temp = damm[temp][digits[i]]
}
return temp == 0
}

console.log("Valid numbers between 5700 and 5800 are:")
for (var i = 5700; i <= 5800; i++) {
if (is_valid(i)) {
process.stdout.write(i + " ")
}
}
console.log("")
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Julia

Julia array indices start at 1, not 0, so the crucial code line (`temp = damm[temp + 1][d - '0' + 1]`) needs to add 1 to the array subscripts when retrieving values from the `damm` matrix.

``````function is_valid(num)
damm = (
(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))
temp = 0
str = string(num)
for d in str
temp = damm[temp + 1][d - '0' + 1]
end
return temp == 0
end

println("Valid numbers between 5700 and 5800 are: ")
for i in 5700:5800
if is_valid(i)
print("\$i ")
end
end
println("")
``````

Output:

``````\$ julia ./damm-algo.jl
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Kotlin

Declaring and initializing a matrix in Kotlin is somewhat painful, but the code is otherwise fairly straight forward.

``````val damm = arrayOf(
intArrayOf(0, 3, 1, 7, 5, 9, 8, 6, 4, 2),
intArrayOf(7, 0, 9, 2, 1, 5, 4, 8, 6, 3),
intArrayOf(4, 2, 0, 6, 8, 7, 1, 3, 5, 9),
intArrayOf(1, 7, 5, 0, 9, 8, 3, 4, 2, 6),
intArrayOf(6, 1, 2, 3, 0, 4, 5, 9, 7, 8),
intArrayOf(3, 6, 7, 4, 2, 0, 9, 5, 8, 1),
intArrayOf(5, 8, 6, 9, 7, 2, 0, 1, 3, 4),
intArrayOf(8, 9, 4, 5, 3, 6, 2, 0, 1, 7),
intArrayOf(9, 4, 3, 8, 6, 1, 7, 2, 0, 5),
intArrayOf(2, 5, 8, 1, 4, 3, 6, 7, 9, 0)
)

fun is_valid(num: Int): Boolean {
val n_str = num.toString()
var temp = 0
for (d in n_str) {
temp = damm[temp][d - '0']
}
return temp == 0
}

fun main() {
println("Valid numbers between 5700 and 5800 are: ")
for (i in 5700..5800) {
if (is_valid(i)) print("\$i ")
}
println("")
}
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Lua

Like in Julia, Lua array indices start at 1, not 0, so the crucial code line (`temp = damm[temp + 1][ch + 1]`) needs to add 1 to the array subscripts when retrieving values from the `damm` matrix.

``````local damm = {
{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}
}
function is_valid(num)
local n_str = tostring(num)
local temp = 0
for ch in n_str:gmatch"." do
temp = damm[temp + 1][ch + 1]
end
return temp == 0
end

print("Valid numbers between 5700 and 5800 are: ")
for i = 5700, 5800 do
if is_valid(i) then
io.write(i, " ")
end
end
print("")
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Nim

Remember that Nim control flow is indentation-based, like Python.

``````import strutils

let damm = [ [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] ]

proc is_valid(num: int): bool =
let n_str = intToStr(num)
var temp = 0
for i in 0..len(n_str) - 1:
temp = damm[temp][int(n_str[i]) - 48]
return temp == 0

echo "Valid numbers between 5700 and 5800 are:"
for i in 5700..5800:
if is_valid(i):
stdout.write i, " "
echo ""
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Pascal

I’m not particularly fond of Pascal, which I found too verbose (at least, by today’s criteria), and I’ve never used it for real-life projects (well, except some quite small Delphi projects a number of decades ago). But, having said that, I must add that Pascal is nonetheless a soft point for me, as it is the first language that I learned in my IS studies (although I had programmed as an autodidact before starting my studies, in Basic, in C, and in the pseudo-assembler of programmable pocket calculators). Pascal is quite clean (perhaps too clean) and it is with Pascal that I first learned the tenets of structured programming. Other languages that I used at the time and found interesting were Fortran, Ada, Prolog, Caml, and especially Modula-2 (or, was it Modula-3? Quite possibly both, one after the other. I’m not quite sure). I might try implementations in some of these languages some day, although I have forgotten most about them. Another language that I also (vaguely) learned at the time of my early studies is Cobol, but I disliked it so much that it is very unlikely that I will ever try to code something in it in the future.

``````program DammCheckDigit;
uses
sysutils;

const damm : array[0..9,0..9] of integer =
( (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) );

function is_valid(num : integer) : boolean;
var
temp, i : integer;
n_str : string;
begin
n_str := inttostr(num);
temp := 0;
for i := 0 to length(n_str) do
begin
temp := damm[temp, ord(n_str[i]) - ord ('0')];
end;
is_valid := temp=0;
end;

var
i : integer;
begin
writeln('Valid numbers between 5700 and 5800 are:');
for i := 5700 to 5800 do
begin
if is_valid(i) then
write(i, ' ');
end;
writeln
end.

{
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
}
``````

#### Damm Algorithm in Python

``````damm = (
(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 is_valid(num: int) -> bool:
temp = 0
for d in str(num):
temp = damm[temp][int(d)]
return temp == 0

print("Valid numbers between 5700 and 5800 are:")
for i in range(5700, 5801):
if is_valid(i):
print(i, end=' ')
print("")
``````

Output:

``````\$ python3 ./damm-algo.py
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Ring

Like in Julia and Lua, array indices start at 1, not 0, so the crucial code line (`temp = damm[temp + 1][ch - '0' + 1]`) needs to add 1 to the array subscripts when retrieving values from the `damm` matrix.

``````damm = [ [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] ]

see "Valid numbers between 5700 and 5800 are:" + nl
for i = 5700 to 5800
if is_valid(i)
see "" + i + " "
ok
next
see " " + nl

func is_valid(num)
temp = 0
n = string(num)
for ch in n
temp = damm[temp + 1][ch - '0' + 1]
next
return temp = 0
``````

Output:

``````\$ ring ./damm-algo.ring
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Ruby

The Ruby implementation is very simple and very concise, thanks to the built-in `digits` function. Note, however, that this function returns the digits in an inverse order, so we need to reverse it.

``````def is_valid (n)
damm = [ [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] ]
temp = 0
for ch in n.digits.reverse
temp = damm[temp][ch]
end
return temp == 0
end

puts("Valid numbers between 5700 and 5800 are:")
for i in 5700..5800
if is_valid(i)
printf("%d ", i)
end
end
puts("")
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Rust

``````fn is_valid(num: u32) -> bool {
static DAMM: [[u8; 10]; 10] = [
[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],
];

let mut temp = 0;
let n_str = num.to_string();
let digits = n_str.bytes();
for i in digits {
temp = DAMM[temp as usize][i as usize - 48];
};
return temp == 0
}

fn main() {
println!("{}", "Valid numbers between 5700 and 5800 are:");
for i in 5700..5800 {
if is_valid(i) {
print!("{} ", i);
}
}
println!("{}", " ");
}
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Scala

``````object DammCheckDigit extends App {
var damm =
Vector(
Vector(0, 3, 1, 7, 5, 9, 8, 6, 4, 2),
Vector(7, 0, 9, 2, 1, 5, 4, 8, 6, 3),
Vector(4, 2, 0, 6, 8, 7, 1, 3, 5, 9),
Vector(1, 7, 5, 0, 9, 8, 3, 4, 2, 6),
Vector(6, 1, 2, 3, 0, 4, 5, 9, 7, 8),
Vector(3, 6, 7, 4, 2, 0, 9, 5, 8, 1),
Vector(5, 8, 6, 9, 7, 2, 0, 1, 3, 4),
Vector(8, 9, 4, 5, 3, 6, 2, 0, 1, 7),
Vector(9, 4, 3, 8, 6, 1, 7, 2, 0, 5),
Vector(2, 5, 8, 1, 4, 3, 6, 7, 9, 0)
)

def is_valid(num: Int): Boolean = {
val num_str = num.toString.getBytes
var temp = 0
for (ch <- num_str) {
temp = damm(temp)(ch - '0')
}
return temp == 0
}

println("Valid numbers between 5700 and 5800 are:")
for (i <- 5700 to 5800) {
if (is_valid(i)) {
printf("%d ", i)
}
}
println("")
}
``````

Output:

``````Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

#### Damm Algorithm in Tcl

As in awk and Dart, I haven’t found a good way to declare and initialize two-dimensional arrays in Tcl, and the documentation is quite sparse. So I used the same solution as in awk and Dart for the conversion matrix: an array of strings. My knowledge of Tcl dates from the 1990s and is very rusty, so I initially had an interpreter error on almost every code line. So, be aware that my implementation certainly doesn’t satisfy the best practices of this language.

``````proc is_valid {n} {
set damm(0) "0317598642"
set damm(1) "7092154863"
set damm(2) "4206871359"
set damm(3) "1750983426"
set damm(4) "6123045978"
set damm(5) "3674209581"
set damm(6) "5869720134"
set damm(7) "8945362017"
set damm(8) "9438617205"
set damm(9) "2581436790"

set temp 0
foreach ch [split \$n {}] {
set row \$damm(\$temp)
set temp [ string index \$row \$ch ]
}
return [ expr \$temp == 0 ? 1 : 0]
}

puts "Valid numbers between 5700 and 5800 are: "
for {set i 5700} {\$i <= 5800} {incr i} {
if [ is_valid \$i ] {
puts -nonewline  "\${i} "
}
}
puts ""
``````

Output:

``````\$ tclsh ./damm-algo.tcl
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797
``````

## Task 2: Palindromic Prime Cyclops

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
``````

### Palindromic Prime Cyclops in Raku

In order to reduce the pointless computations, we’ll only test number ranges with an odd number of digits (`100..999, 10000..99999, 1000000..9999999`). As it turns out, the process is quite fast (about 2.6 seconds), so that performance enhancement wasn’t really required. I find it nonetheless better to avoid useless computations.

``````sub is-cyclops (\$n) {
my \$length = \$n.chars;
return False if \$length %% 2;
my \$mid = (\$length - 1) /2;
return False if substr(\$n, \$mid, 1) != 0;
return False if \$n.comb[0..\$mid-1] ~~ /0/;
return False if \$n.comb[\$mid+1..\$length-1] ~~ /0/;
return True;
}

my \$count = 0;
for |(100..999), |(10000..99999), |(1000000..9999999) -> \$i {
next unless \$i eq \$i.flip;
next unless \$i.is-prime;
if is-cyclops \$i {
print "\$i ";
\$count++;
last if \$count == 20;
}
}
say "";
``````

This program displays the following output:

``````\$ time raku ./cyclops.raku
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251

real    0m2,573s
user    0m0,015s
sys     0m0,015s
``````

### Palindromic Prime Cyclops in Perl

This is a port to Perl of the Raku program above. Since Perl doesn’t have a built-in `is_prime` subroutine, we roll out our own.

``````use strict;
use warnings;
use feature qw/say/;

sub is_cyclops {
my \$n = shift;
my \$len = length \$n;
return 0 if \$len % 2 == 0;
my \$mid = (\$len - 1) /2;
return 0 if substr(\$n, \$mid, 1) != 0;
return 0 if (split //, \$n)[0..\$mid-1] =~ /0/;
return 0 if (split //, \$n)[\$mid+1..\$len-1] =~ /0/;
return 1;
}

sub is_prime {
my \$n = shift;
return 1 if \$n == 2;
return 0 if \$n % 2 == 0;
return 0 if \$n == 1;
my \$p = 3;
my \$sqrt = sqrt \$n;
while (\$p <= \$sqrt) {
return 0 if \$n % \$p == 0;
\$p += 2;
}
return 1;
}

my \$count = 0;
for my \$i (100..999, 10000..99999, 1000000..9999999) {
next unless \$i eq reverse \$i;
next unless is_cyclops \$i;
if (is_prime \$i) {
print "\$i ";
\$count++;
last if \$count == 20;
}
}
``````

This program displays the following output:

``````\$ perl ./cyclops.pl
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
``````

### Palindromic Prime Cyclops in Other Languages

We now present the same palindromic prime cyclop implementations in the following 8 guest languages:

• Julia
• JavaScript
• Kotlin
• Lua
• Python
• Ring
• Ruby
• Coconut

#### Palindromic Prime Cyclops in Julia

I like the concision of Perl and Raku postfix conditionals such as:

``````return False if substr(\$n, \$mid, 1) != 0;
return False if \$n.comb[0..\$mid-1] ~~ /0/;
return False if \$n.comb[\$mid+1..\$length-1] ~~ /0/;
return True;
``````

In most other languages, you would need three code lines for each case, for example in JavaScript:

``````if (s[mid] != '0') {
return false
}
if (s.slice(0, mid-1).search('0') >= 0) {
return false
}
if (s.slice(mid+1).search('0') >= 0) {
return false
}
return true
``````

Julia doesn’t have postfix conditionals, but you can use short-circuit evaluation of the `&&` and `||` operators as an alternative to short `if` statements to reach the same concision.

The short-circuit evaluation, which is common to most imperative programming languages, means that:

• In the expression a && b, the subexpression b is only evaluated if a evaluates to true.
• In the expression a || b, the subexpression b is only evaluated if a evaluates to false.

Instead of `if <cond> <statement> end`, one can write `<cond> && <statement>` (which could be read as: `<cond> and then <statement>`). Similarly, instead of `if ! <cond> <statement> end`, one can write || (which could be read as: `<cond> or else <statement>`). This idiomatic alternative to short `if` statement is frequently used in Julia. Although most languages have the short-circuit behavior of logical operators, not many of them support this construct with an ending statement. Raku and Perl do, but this is not commonly used because the `return false if ...` is admittedly clearer. In the seven guest languages used here, only Kotlin also supports this construct.

So, in Julia, we will have, for example:

``````len % 2 == 0 && return false
...
s[mid] == '0' || return false
``````

This is our Julia implementation using this concise construct:

``````using Primes

function is_cyclops(n)
s = string(n)
len = length(s)
len % 2 == 0 && return false
mid = Int((len + 1) /2)
s[mid] == '0' || return false
if occursin('0', s[1:mid-1]) || occursin('0', s[mid+1:len])
return false
end
return true;
end

count = 0
for i = [101:999; 10000:99999; 1000000:9999999]
string(i) != reverse(string(i)) && continue
is_cyclops(i) || continue
if isprime(i)
print("\$i ")
global count += 1
count >= 20 && break
end
end
println("")
``````

Output:

``````\$ julia ./cyclop.jl
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
``````

#### Palindromic Prime Cyclops in JavaScript

JavaScript doesn’t have a built-in function for prime numbers (just as almost all other guest languages to follow). So we roll out our own `is_prime` function (ported from the Perl implementation above).

It also doesn’t seem possible to combine ranges as we’ve done previously in other languages, so we use a `if ... else if ... else if ...` construct to simulate range concatenation.

``````function is_cyclops (n) {
let s = n.toString()
let len = s.length
if (len % 2 == 0) {
return false
}

let mid = (len - 1) / 2
if (s[mid] != '0') {
return false
}

if (s.slice(0, mid-1).search('0') >= 0) {
return false
}
if (s.slice(mid+1).search('0') >= 0) {
return false
}
return true
}

function is_prime(n) {
if (n == 2) {
return true
}
if (n < 2 || n % 2 == 0) {
return false
}
var p = 3
let sqrt_n = Math.sqrt(n)
while (p <= sqrt_n) {
if (n % p == 0) {
return false
}
p += 2
}
return true
}

var count = 0
var i = 100
while (count < 20) {
i++
if (i == 999) {
i = 10000
} else if (i == 99999) {
i = 1000000
} else if (i >= 9999999) {
break
}
if (i.toString() != i.toString().split("").reverse().join("")) {
continue;
}
if (! is_cyclops(i)) {
continue;
}
if (is_prime(i)) {
process.stdout.write(i + " ")
count++
}
}
console.log("")
``````

Output:

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

#### Palindromic Prime Cyclops in Kotlin

I do not know whether the short-circuit evaluation alternative to short `if` statement described above in the context of the Julia language is as commonly used in Kotlin as it is in Julia, but, since it works in Kotlin, I’ll use it here. Also note that we need to implement our own `is_prime` function in Kotlin.

``````fun is_prime(n: Int): Boolean {
n == 2 && return true
if (n < 2 || n % 2 == 0) {
return false
}
var p = 3
val sqrt_n : Int = Math.sqrt(n.toDouble()).toInt()
while (p <= sqrt_n) {
n % p == 0 && return false
p += 2
}
return true
}

fun is_cyclops(num: Int): Boolean {
val s = num.toString()
val len = s.length
len % 2 == 0 && return false
val mid = ((len - 1) /2).toInt()
s[mid] == '0' || return false
if ('0' in s.slice(0 until mid) or '0' in s.slice(mid+1 until len) {
return false
}
return true
}

fun main() {
var count = 0
var i = 100
while (count < 20) {
i++
if (i == 999) {
i = 10000
} else if (i == 99999) {
i = 1000000
} else if (i >= 9999999) {
break
}
if (i.toString() != i.toString().reversed()) {
continue;
}
if (! is_cyclops(i)) {
continue;
}
if (is_prime(i)) {
print("\$i ")
count++
}
}
println(" ")
}
``````

Output:

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

#### Palindromic Prime Cyclops in Lua

Lua doesn’t have a `next` or `continue` statement to go directly to the next iteration of a loop, because “the language is designed to be small.” I’m not sure it is a very good reason, as, in my humble opinion, this kind of statement is very useful. This is the reason for which we have two `goto skip` statements in the main part of the program. I know very well what Edsger Dijkstra said in his famous letter to ACM “Go To Statement Considered Harmful,” but Donald Knuth commented that a “goto forward” within the same routine wasn’t that bad. This is the case here. Having said that, I would definitely prefer if Lua had a `continue` or `next` statement rather than a `goto` statement.

We also have to implement a `is_prime` function here.

``````local function is_cyclops(num)
local n_str = tostring(num)
size = string.len(n_str)
if size % 2 == 0 then
return false
end
mid = (size + 1) / 2
if string.sub(n_str, mid, mid ) ~= '0' then
return false
end
if string.sub(n_str, 1, mid-1):find "0" ~= nil then
return false
end
if string.sub(n_str, mid+1, len):find "0" ~= nil then
return false
end
return true
end

local function is_prime(n)
if n == 2 then
return true
end
if n < 2 or n % 2 == 0 then
return false
end
local p = 3
sqrt_n = math.sqrt(n)
while p <= sqrt_n do
if n % p == 0 then
return false
end
p = p + 2
end
return true
end

count = 0
i = 100
while count < 20 do
i = i + 1
if i == 999 then
i = 10000
elseif i == 99999 then
i = 1000000
elseif i >= 9999999 then
break
end

if i ~= tonumber(string.reverse(tostring(i))) then
goto skip
end
if not is_cyclops(i) then
goto skip
end
if is_prime(i) then
io.write(i, " ")
count = count + 1
end
::skip::
end
print("")
``````

Output:

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

#### Palindromic Prime Cyclops in Python

``````import math
from re import search
from itertools import chain

def is_prime(n):
if n == 2:
return True
if n == 0 or n == 1 or n % 2 == 0:
return False
p = 3
sqrt_n = math.sqrt(n)
while (p <= sqrt_n):
if ((n % p) == 0):
return False
p += 2
return True

def is_cyclops (num):
s = str(num)
size = len(s)
if size % 2 == 0:
return False
mid = int((size - 1) / 2)
if s[mid] != '0':
return False
if search(r"0", s[0:mid-1]) or search(r"0", s[mid+1:size-1]):
return False
return True

count = 0
myrange = chain(range(100, 999), range(10000, 99999), range(1000000, 9999999))
for i in myrange:
if str(i) != str(i)[::-1]:
continue
if not is_cyclops(i):
continue
if is_prime(i):
print(i, end=' ')
count += 1
if count >= 20:
break

print("")
``````

Output:

``````\$ python3 ./cyclop.py
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
``````

#### Palindromic Prime Cyclops in Ring

As far as I can tell, Ring also doesn’t have `continue` or `next` statements (and also no `last` and no `break`). Or, at least, I couldn’t find them (or an equivalent) in the documentation. So I had to use nested `if` statements, something that I don’t like too much. It also appears that there is no built-in function for reversing a string, so I wrote a `is_palindrome` function. And also a `is_prime` function. Also note that the equality operator (`==` in many languages) is spelled with a single equal sign in Ring, so we have for example `if n % p = 0`. I wonder how the compiler can distinguish it from the assignment operator, there must be some cases that are ambiguous.

``````i = 100
count = 0
while count < 20
i++
if i = 999
i = 10000
ok
if i = 99999
i = 1000000
ok
if is_palindrome(i)
if is_cyclops(i)
if is_prime(i)
count++
see "" + i + " "
ok
ok
ok
end
see "" + nl

func is_prime (n)
if n = 2
return true
ok
if n < 2 or n % 2 = 0
return false
ok
p = 3
sqrt_n = sqrt(n)
while p < sqrt_n
if n % p = 0
return false
ok
p++
end
return true

func is_cyclops(n)
s = "" + n
size = len(s)
if size % 2 = 0
return false
ok
mid = ( size + 1) / 2
if s[mid] != 0
return false
ok

if substr(left(s, mid-1), "0") > 0
return false
ok
if substr(right(s, mid-1), "0") > 0
return false
ok
return true

func is_palindrome(n)
s = "" + n
size = len(s)
for i = 1 to size/2
if s[i] != s[size - i + 1]
return false
ok
next
return true
``````

Output:

``````\$ ring  ./cyclop.ring
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
``````

#### Palindromic Prime Cyclops in Ruby

Ruby has a built-in `prime` function, so we don’t need to implement it. I found a way to combine ranges, but I must admit that this is copied from a post on Stack Overflow, I would not have found it by myself.

``````require 'prime'

def is_cyclops (num)
s = num.to_s
len = s.length;
if len % 2 == 0 then
return false
end
mid = (len - 1) / 2
if s[mid] != '0' then
return false
end
if s[0..mid-1][/0/] || s[mid+1..len-1][/0/]
return false
end
return true
end

count = 0;
range = [ 100..999, 10000..99999, 1000000..9999999 ].map { |r| Array(r) }.inject( :+ )
for i in range
if i.to_s != i.to_s.reverse || ! is_cyclops(i)
next
end
if i.prime?
printf("%d ", i)
count += 1;
if count == 20
break
end
end
end
puts ""
``````

Output:

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

#### Palindromic Prime Cyclops in Coconut (a Functional Extension of Python)

This section on Coconut was added on August 18, 2022.

Coconut is a variant of Python built for functional programming. It is actually a kind of extension of Python, and Coconut code is in fact compiled to Python code. The documentation is still somewhat limited, but there is a good Coconut Tutorial and a reference Coconut Documentation.

I was interested in trying to use Coconut for this task essentially because of its support to pipeline style programming. Since we’re looking for the first twenty integers having a certain set of properties (prime, palindromic, with an odd number of digits, with a 0 in the middle and no other 0, etc.), it is appealing to use a pipeline of filters, one for each of these properties, as done in the last (main) section of the code below.

``````import math
from re import search

def is_prime(n):
case n:
match 0:
return False
match 1:
return False
match 2:
return True
match _ is int if n > 2:
if n % 2 == 0:
return False
p = 3
sqrt_n = math.sqrt(n)
while (p <= sqrt_n):
if (n % p) == 0:
return False
p += 2
return True

def is_cyclops (num):
s = str(num)
size = len(s)
mid = int((size - 1) / 2)
if s[mid] != '0':
return False
if search(r"0", s[0:mid-1]) or search(r"0", s[mid+1:size-1]):
return False
return True

range(100, 999) :: range(10000, 99999) :: range(1000000, 9000000) \
|> filter\$( -> str(_) == str(_)[::-1]) \    # palindrome
|> filter\$( -> len(str(_)) %2 != 0) \       # odd number of digits
|> filter\$(is_cyclops) |> filter\$(is_prime) \
|>  list |> .\$[:20] |> print
``````

Output:

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

## Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on August 21, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.