## 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.

## # Perl Weekly Challenge 176: Permuted Multiples and Reversible Numbers

These are some answers to the Week 176 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. 7, 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.

Write a script to find the smallest positive integer `x` such that `x`, `2x`, `3x`, `4x`, `5x` and `6x` are permuted multiples of each other.

For example, the integers 125874 and 251748 are permuted multiples of each other as

``````251784 = 2 x 125874
``````

and also both have the same digits but in different order.

Output

``````142857
``````

In Raku, Perl, and some other programming languages, conversions between numbers and strings are simple or even implicit and automatic. This task will be very easy for them. In some other languages, the strong typing system might make it more difficult. In such an event, we may also use a purely arithmetic method to retrieve the individual digits (see for example the C and bc implementations). This may have an impact on my choice of guest languages: I will not try guest languages that are crippled by a type system straitjacket.

### Permuted Multiples in Raku

We’re essentially trying to find if the first six integer multiples of an integer are anagrams of each other. One way to go might be to store the individual digits in a hash and check whether we have the same digits. But it’s not so easy when the input number has twice or several times the same digit. It is usually easier (and probably faster) to reduce the input number to a normalized form (for example with the digits rearranged in ascending order) and to compare the normalized form of the input number with the normalized forms of the multiples. In the program below, the `ordered` variable is a string in which the digits of the input integer have been rearranged in ascending order. At the end, we only need a string comparison to find out whether the various integers have the same digits.

``````sub check_multiples (\$j) {
my \$ordered = join '', \$j.comb.sort;
for 2..6 -> \$k {
return False if (\$k * \$j).comb.sort.join ne \$ordered;
}
return True;
}

.say and last if check_multiples \$_ for 1..Inf;
``````

This program displays the following output:

``````\$ time raku ./permuted-multiples.raku
142857

real    0m3,370s
user    0m0,015s
sys     0m0,088s
``````

We can significantly improve performance by adding one code line at the beginning of the `check_multiples` subroutine:

``````sub check_multiples (\$j) {
return False if \$j.chars != (6 * \$j).chars;
my \$ordered = join '', \$j.comb.sort;
for 2..6 -> \$k {
return False if (\$k * \$j).comb.sort.join ne \$ordered;
}
return True;
}
``````

By returning early from the subroutine when the length of `6 * \$j` is more than the length of `\$j` we save quite a bit of useless computations. The execution time goes down to 1.390 sec. Another possibility would be to reverse the tests in the `for` loop, i.e. to go down from 6 to 2.

### Permuted Multiples in Perl

This is a port to Perl of the Raku program above. Please refer to the description in the Raku section above in you need explanations.

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

sub check_multiples {
my \$j = shift;
my \$ordered = join '', sort split //, \$j;
for my \$k (2..6) {
return 0 if \$ordered ne join '', sort {\$a cmp \$b}  split //, (\$k * \$j);
}
return 1;
}

my \$i = 1;
while (1) {
if (check_multiples \$i) {
say \$i;
last;
}
\$i++;
}
``````

This program displays the following output:

``````\$ time perl  permuted-multiples.pl
142857

real    0m0,604s
user    0m0,546s
sys     0m0,046s
``````

The Perl code is a bit longer than the Raku code, but the Perl program runs 5,6 times faster.

### Permuted Multiples in Julia

In Julia, the built-in `digits` function returns the digits of a number. No need for conversions between integer and string and the other way around, and this leads to a quite concise program.

``````function check_multiples(n)
ordered = sort(digits(n))
for j in 2:6
if sort(digits(n * j)) != ordered
return false
end
end
return true
end

i = 1
while true
if check_multiples(i)
println(i)
break
end
global i += 1
end
``````

Output:

``````\$ julia .\permuted-multiples.jl
142857
``````

### Permuted Multiples in Python

``````def check_multiples(n):
input = [int(c) for c in str(n)]
input.sort()
for i in range(2, 7):
test = [int(c) for c in str(n * i)]
test.sort()
if input != test:
return False
return True

i = 2
while True:
if check_multiples(i):
print(i)
break
i += 1
``````

Output:

``````\$ time python3 ./permuted-multiples.py
142857

real  0m0,745s
user  0m0,640s
sys   0m0,077s
``````

### Permuted Multiples in awk

The awk language is relatively slow, so I added a test:

``````        if (length(test) != len) {
return 0
}
``````

before the inner `for` loop to immediately go out of the loop and avoid the digit-by-digit comparison if the length of tested number is not the same as the length of the input number.

``````function check_multiples(n) {
split(n, ordered, "")
asort(ordered)
len = length(ordered)
for (j = 2; j <= 6; j++) {
split(n * j, test, "")
asort(test)
if (length(test) != len) {
return 0
}
for (k = 1; k <= len; k++) {
if (ordered[k] != test[k]) {
return 0
}
}
}
return 1
}

BEGIN  {
i = 1
while (1) {
if (check_multiples(i)) {
print i
break
}
i++
}
}
``````

With the performance improvement described above, the runtime is quite good:

``````\$ time awk -f permuted-multiples.awk
142857

real    0m1,498s
user    0m1,343s
sys     0m0,015s
``````

However, we can improve it by making the test earlier in the `check_multiples` function:

``````function check_multiples(n) {
if (length(n) != length(6 * n)) {
return 0
}
split(n, ordered, "")
asort(ordered)
len = length(ordered)
for (j = 2; j <= 6; j++) {
split(n * j, test, "")
asort(test)
for (k = 1; k <= len; k++) {
if (ordered[k] != test[k]) {
return 0
}
}
}
return 1
}
``````

With this change, the output is now this:

``````\$ time awk -f permuted-multiples.awk
142857

real    0m0,653s
user    0m0,624s
sys     0m0,031s
``````

That’s 2.3 times faster. Not bad.

### Permuted Multiples in C

The C implementation is quite verbose (and sort of a pain in the neck to get it right) compared to other languages, but I decided not to criticize this aspect any further when I saw the performance (barely more than 1/10 sec. runtime):

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

int comp (const void * elem1, const void * elem2) {
int f = *((int*)elem1);
int s = *((int*)elem2);
if (f > s) return  1;
if (f < s) return -1;
return 0;
}

int normalize (int num) {
int n = num;
int len = n <= 9 ? 1 : floor(log10(n)) + 1;
int d[len];  // array of digits of input number
char st[len];
int i = 0;
while (n > 0) {
d[i] = n % 10;
n /= 10;
i++;
}
qsort (d, sizeof(d)/sizeof(*d), sizeof(*d), comp);
int norm = 0;
int j = 1;
for (int i = len - 1; i >= 0; i--) {
norm += d[i] * j;
j *= 10;
}
return norm;
}

int permuted_multiples (int n) {
int norm_in = normalize(n);
for (int i = 6; i > 2; i--)
if (normalize(n * i) != norm_in) return 0;
return 1;
}

int main () {
int i = 1;
while (1) {
if (permuted_multiples(i)) {
printf("%d\n", i);
break;
}
i++;
}
}
``````

Output:

``````\$ time ./a.out
142857

real    0m0,112s
user    0m0,078s
sys     0m0,000s
``````

### Permuted Multiples in D

D is similar to C, but with less pointer hassle and more built-in functions, making the syntax simpler:

``````import std.stdio;
import std.conv, std.array;
import std.algorithm;

int normalize(int num) {
string n = to!string(num, 10);
ulong len = n.length;
string[] d = n.split("");
d.sort();
}

bool permuted_multiples (int n) {
int norm_in = normalize(n);
for (int i = 6; i > 2; i--)
if (normalize(n * i) != norm_in) return false;
return true;
}

void main() {
int i = 1;
while (true) {
if (permuted_multiples(i)) {
printf("%d\n", i);
break;
}
i++;
}
writeln(" ");
}
``````

This program also displays 142857 and runs in .44 second (don’t compare with C, though, the timings are not equivalent for various reasons).

Write a script to find out all Reversible Numbers below 100.

A number is said to be a reversible if sum of the number and its reverse had only odd digits.

For example,

``````36 is reversible number as 36 + 63 = 99 i.e. all digits are odd.
17 is not reversible as 17 + 71 = 88, none of the digits are odd.
``````

Output:

``````10, 12, 14, 16, 18, 21, 23, 25, 27,
30, 32, 34, 36, 41, 43, 45, 50, 52,
54, 61, 63, 70, 72, 81, 90
``````

### Reversible Numbers in Raku

I first thought about using junctions to check whether all of the digits of the resulting number are odd (or, alternatively, whether any of the digits is even), but it rapidly occurred to me that a regex character class with all even digits is sort of equivalent to a junction with even digits, and that a regex solution would be much simpler (and, by the way, that the same solution could also be used in Perl (and possibly some other languages).

This leads to the following very simple code:

``````print "\$_ " unless \$_ + .flip ~~ /<[02468]>/ for 1..100;
``````

Used as a Raku one-liner, we obtain the following output:

``````\$ raku -e 'print "\$_ " unless \$_ + .flip ~~ /<[02468]>/ for 1..100;'
10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Perl

The Perl solution also uses a regex and an even-digit character class to do the job:

``````for (1..100) {print "\$_ " unless (\$_ + reverse \$_) =~ /[02468]/}
``````

Used as a Perl one-liner, we obtain the following output:

``````\$ perl -e 'for (1..100) {print "\$_ " unless (\$_ + reverse \$_) =~ /[02468]/}'
10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Julia

Julia uses the Perl Compatible Regular Expressions (PCRE) library to handle regexes. The `occursin` function returns a Boolean value telling us whether the regex pattern was found. This is almost as easy as in Raku and Perl

``````for i in 1:100
sum = i + parse(Int32, reverse(string(i)))
if ! occursin(r"[02468]", string(sum))
print("\$i ")
end
end
println(" ")
``````

Output:

``````\$ julia .\reversible.jl
10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in C

The C language doesn’t have a standard string reverse function (although some implementations have it). So, we have to write one. Otherwise, we convert the integer sum to a string (using the `sprintf` function) and loop through the digits to check whether any of them is even, and return a false value (0) if such is the case.

``````int reverse(int n) {
char st[10];
char r[10];
int len = sprintf(st, "%d", n);   // convert input int to string
for (int i = 0; i < len; i++) {
r[len - i - 1] = st[i];
}
r[len] = '\0';
return atoi(r);
}

int is_reversible(int n) {
char sum[10];
int length =  sprintf(sum, "%d", n + reverse(n));
for (int k = 0; k < length; k++) {
if (sum[k] % 2 == 0) {
return 0;
}
}
return 1;
}

int main () {
for (int i = 1; i < 100; i++) {
if (is_reversible(i)) {
printf("%d ", i);
}
}
printf("%s\n", "");
}
``````

Output:

``````\$ ./a.out
10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

#### C compared to Perl or Raku

If you compare this 35-line C solution with the Raku or Perl one-liners shown above, you’ll probably understand why Raku and Perl are my favorite programming languages. Having said that, I should add that C, which was created in the early 1970s and is still very much in use half a century later, is sort of the mother of all languages (even the Perl interpreter is written mostly in C). And, as seen above in the context of the first task of this challenge, C is very fast.

For those of you old enough to remember the Usenet newsgroups, let me share this pearl of wisdom dating from the late 1990s.

A Tribute to the Beatles “Let It Be” (and to Dennis M. Ritchie).

To the tune of “Let It Be”.

To listen to it, go there.

When I find my code in tons of trouble, Friends and colleagues come to me, Speaking words of wisdom: Write in C.

As the deadline fast approaches, And bugs are all that I can see, Somewhere, someone whispers: Write in C.

Write in C, write in C, Write in C, oh, write in C. LOGO’s dead and buried, Write in C.

### Reversible Numbers in D

The D programming language boasts to combine the performance and safety of compiled languages (such as C or C++) with the expressive power of modern dynamic and functional programming languages. The syntax is relatively close to C, but the program is notably shorter than its C counterpart. Here, we have methods to reverse a string (`retro`) and to easily convert integers to strings or strings to integers. As with our C implementation, we loop through the digits to check whether any of them is even, and return `false` if such is the case.

``````import std.stdio;
import std.conv, std.range;

bool is_reversible(int n) {
string s = to!string(n, 10);
string rev = s.retro.text;
string sum = to!string(n + to!int(rev), 10);
for (int k = 0; k < sum.length; k++) {
if (sum[k] % 2 == 0) {
return false;
}
}
return true;
}

void main() {
for (int i = 1; i < 100; i++) {
if (is_reversible(i)) {
printf("%d ", i);
}
}
writeln(" ");
}
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in bc

bc stands for “basic calculator” and was initially written almost half a century ago. As a (programmable) calculator, bc can run mathematical or arithmetic scripts, but it has no string manipulation features. So we use only arithmetical tools here.

``````define reverse (n) {
sum = 0
j = 10 ^ (length(n) - 1)
while (n > 0) {
sum += (n % 10) * j
n = n/10
j /= 10
}
return (sum )
}

define is_reversible(m) {
sum = m + reverse(m)
while (sum > 0) {
k = sum % 10
if (k % 2 == 0) {
return 0
}
sum /= 10
}
return 1
}

for (i = 1; i <= 100; i++) {
# print i, " "
if (is_reversible(i)) {
print i, " "
}
}
quit
``````

Output:

``````\$ bc -q reversible.bc
10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72\
81 90
``````

### Reversible Numbers in awk

Compared to bc, awk has some limited string manipulation features (such as `substr`) that we put to good use here. awk also has some regex capabilities, but they’re associated with standard input (e.g. files) reading and did not seem to be usable in our context. So, our program is essentially based on arithmetic loops.

``````function is_reversible(n) {
len = length(n)
m = ""
for (j = len; j != 0; j--) {
m = m substr(n, j, 1)
}
sum = m + n
len = length(sum)
for (k = 1; k <= len; k++) {
if ((substr(sum, k, 1) % 2) == 0) {
return 0
}
}
return 1
}

BEGIN {
for (i = 1; i <= 200; i++) {
if (is_reversible(i)) {
printf("%d ", i)
}
}
}
``````

Output:

``````\$ awk -f ./reversible.awk
10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Python

In Python, we use the features provided by the `re` regex library, leading to a fairly concise program.

``````from re import search
pattern = r"[02468]"
for i in range(1, 100):
tested = str(i + int(str(i)[::-1]))
if not search(pattern, tested):
print(i, end=' ')
``````

Output:

``````\$ python3 ./reversible.py
10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Ruby

I really like Ruby’s ability to chain method invocations as in `sum = n + n.to_s.reverse.to_i`, which makes it possible to convert an integer to a string, to revert the string, to convert the resulting string back to an integer and finally finally to add it to another number, all in one short code line. We’ve done similar chained data conversions in Perl, Raku and Julia, but there is a number of mainstream programming languages which can’t do that (mostly because their built-in methods or functions often have side effects and are intrinsically not pure.

``````def is_reversible(n)
sum = n + n.to_s.reverse.to_i
while (sum > 0)
k = sum % 10
if k % 2 == 0
return false
end
sum /= 10
end
return true
end

for i in 1..100
if is_reversible(i)
printf("%d ", i)
end
end
puts("")
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Scala

Scala also provides the pleasant possibility to chain method invocations (as in `var sum = n + n.toString.reverse.toInt`). So, our Scala program looks quite similar to our Ruby implementation.

``````object reversible extends App {
def is_reversible(n: Int): Boolean = {
var sum = n + n.toString.reverse.toInt
while (sum > 0) {
val k = sum % 10
if (k % 2 == 0) {
return false
}
sum /= 10
}
return true
}

for (i <- 1 to 100) {
if (is_reversible(i)) {
printf("%d ", i)
}
}
println("")
}
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Ring

``````for i = 1 to 100
if is_reversible(i)
see "" + i + " "
ok
next

func reverse(num)
n = "" + num
rev = ""
for i = len(n) to 1 step -1
rev +=  n[i]
next
return number(rev)

func is_reversible (m)
sum = m + reverse(m)
st = "" + sum
for i = 1 to (len(st))
if st[i] % 2 = 0
return false
ok
next
return true
``````

Output:

``````\$ ring ./reversible.ring
10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in JavaScript

``````function is_reversible (n) {
var digits = n.toString().split("")
let reverse_digits = digits.reverse()
let reverse_n = parseInt(reverse_digits.join(""));
var sum = n + reverse_n
while (sum > 0) {
let k = sum % 10
if (k % 2 == 0) {
return false
}
sum = Math.floor(sum / 10)
}
return true
}

for (var i = 1; i <= 100; i++) {
if (is_reversible(i)) {
process.stdout.write(i + " ")
}
}
process.stdout.write(" \n")
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Nim

I tried to use the `split` function with an empty string as a delimiter, but Nim’s `split` function apparently does not accept an empty string. Looking for a solution on the Internet, I found on this Stack Overflow page that a Nim string is a sequence of chars, so that a simple cast (e.g. `@(intToStr(n)`) will split the string into individual chars.

``````import strutils
import algorithm

proc is_reversible(n: int): bool =
# A Nim string is a sequence of chars, so that a cast will
# split the string into individual chars
let rev = parseInt(join(@(intToStr(n)).reversed(), ""))
var sum = n + rev
while sum > 0:
let k = sum mod 10
if (k mod 2 == 0):
return false
sum = (sum / 10).int
return true

for i in 1..100:
if is_reversible(i):
stdout.write i, " "
echo ""
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Dart

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

void main() {
for (int i = 0; i <= 100; i++ ) {
if (is_reversible(i)) {
stdout.write("\$i ");
}
}
}

bool is_reversible(n) {
var rev = int.parse(n.toString().split("").reversed.join(""));
var digits = (n + rev).toString().split("");
int len = digits.length;
for (int i = 0; i < len; i++) {
if (int.parse(digits[i]) % 2 == 0) {
return false;
}
}
return true;
}
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Kotlin

``````fun is_reversible(n: Int): Boolean {
val sum = n + n.toString().reversed().toInt()
val sumstr = sum.toString()
for (i in 1..sumstr.length) {
if (sumstr[i-1].toInt() % 2 == 0) {
return false
}
}
return true
}

fun main() {
for (i in 1..100) {
if (is_reversible(i)) {
print("\$i ")
}
}
println(" ")
}
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Java

My Java implementation of the reversible numbers task is faithful to Java’s reputation of being very verbose.

``````public class ReversibleNumbers {

public static int reverse(int n) {
String n_str = String.valueOf(n);
String rev = "";
char ch;
for (int i = 0; i < n_str.length(); i++) {
ch = n_str.charAt(i);   //extracts each character
rev = ch + rev;         //adds each character in front of the existing string
}
return Integer.parseInt(rev);
}

public static boolean isReversible(int n) {
int sum = n + reverse(n);
char[] digits = String.valueOf(sum).toCharArray();
for (int i = 0; i < digits.length; i++) {
if ((digits[i] - '0') % 2 == 0) {
return false;
}
}
return true;
}

public static void main(String[] args) {
for (int i = 1; i <= 100; i++) {
if (isReversible(i)) {
System.out.printf("%d ", i);
}
}
System.out.printf("%s", "\n");
}
}
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Lua

``````local function is_reversible(n)
rev = tonumber(string.reverse(tostring(n)))
sum = rev + n
while sum > 0 do
if sum % 2 == 0 then
return false
end
sum = math.floor(sum / 10)
end
return true
end

for i = 1, 100 do
if is_reversible(i) then
io.write(i, " ")
end
end
print("")
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

### Reversible Numbers in Go

For some reason, programming languages maintained by groups of dedicated open-source users, such as Raku, Perl, Julia, Nim, JavaScript, Scala, Kotlin, and Lua, have an off-the-shelf `reverse` function or method, whereas programming languages maintained by very big corporations, such as Java or Go, don’t have it, in spite of their huge financial resources. It appears that the open-source model is more efficient. IT managers should think about it: the best programming languages might not be what they think.

``````package main

import (
"fmt"
"strconv"
)

func reverse(n int) int {
n_str := strconv.Itoa(n)
rev := ""
for _, v := range n_str {
rev = string(v) + rev
}
rev_num, _ := strconv.Atoi(rev)
return rev_num
}

func is_reversible(n int) bool {
sum := n + reverse(n)
sum_str := strconv.Itoa(sum)
for i := 0; i < len(sum_str); i++ {
if sum_str[i] % 2 == 0 {
return false
}
}
return true
}

func main() {
for i := 1; i <= 100; i++ {
if is_reversible(i) {
fmt.Printf("%d ", i)
}
}
fmt.Println("")
}
``````

Output:

``````10 12 14 16 18 21 23 25 27 30 32 34 36 41 43 45 50 52 54 61 63 70 72 81 90
``````

## 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 14, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.

## Perl Weekly Challenge 175: Last Sunday and Perfect Totient Numbers

These are some answers to the Week 175 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 July 31, 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.

Write a script to list Last Sunday of every month in the given year.

For example, for year 2022, we should get the following:

``````2022-01-30
2022-02-27
2022-03-27
2022-04-24
2022-05-29
2022-06-26
2022-07-31
2022-08-28
2022-09-25
2022-10-30
2022-11-27
2022-12-25
``````

### Last Sunday in Raku

In Raku, the Date classmethodday-of-month) provides all the methods needed to properly manage dates.

The `MAIN` subroutine takes one parameter, the year that we want to process, and will default to 2022 if no parameter is passed.

First, we compute the last date in the month, find on which day of the week it falls (day of week is an integer between 1 and 7, where 1 stands for Monday and 7 for Sunday).

To get the date in month of the last Sunday in the month, we simply subtract the day of the week from the day in the month, except that this would not work properly when the last day of the month is a Sunday (we would obtain the previous Sunday), so we subtract the week day modulo 7.

``````sub MAIN (Int \$yr = 2022) {
for ('01'..'09', 10 .. 12).flat -> \$month {
my \$month-end = Date.new("\$yr-\$month-01").last-date-in-month;
my \$week_day = \$month-end.day-of-week;
my \$day-in-month = \$month-end.day-of-month;
# Note: Sunday is weekday 7
my \$sunday = \$day-in-month - (\$week_day % 7);
say Date.new("\$yr-\$month-\$sunday");
}
}
``````

This program displays the following output:

``````\$ raku ./last-sunday.raku
2022-01-30
2022-02-27
2022-03-27
2022-04-24
2022-05-29
2022-06-26
2022-07-31
2022-08-28
2022-09-25
2022-10-30
2022-11-27
2022-12-25

~
\$ raku ./last-sunday.raku 2023
2023-01-29
2023-02-26
2023-03-26
2023-04-30
2023-05-28
2023-06-25
2023-07-30
2023-08-27
2023-09-24
2023-10-29
2023-11-26
2023-12-31
``````

### Last Sunday in Perl

This Perl program essentially follows the same idea as the Raku program above, except that we need to compute manually the last day in the month, which leads us to implement an `is_leap` subroutine to be sure of the last day of February.

``````#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;
use Time::Local;

my \$yr = shift // 2022;
my @months = (0, 31, is_leap(\$yr) ? 29 : 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);

for my \$month (1..12) {
my \$month_last_day = timegm( 0, 0, 0, \$months[\$month], \$month - 1, \$yr - 1900 );
my \$day_in_week = (gmtime \$month_last_day)[6];
my \$sunday = \$months[\$month] - (\$day_in_week % 7);
printf "%04d/%02d/%02d\n", \$yr, \$month, \$sunday;
}

sub is_leap {
my \$yr = shift;
return 0 if \$yr % 4;    # no if not divisible by 4
return 1 if \$yr % 100;  # yes if divisible by 4 but not by 100
return 0 if \$yr % 400;  # no if divisible by 100 and not by 400
return 1;               # yes if divisibe by 400
}
``````

This program displays the following output:

``````\$ perl ./last-sunday.pl
2022/01/30
2022/02/27
2022/03/27
2022/04/24
2022/05/29
2022/06/26
2022/07/31
2022/08/28
2022/09/25
2022/10/30
2022/11/27
2022/12/25

~
\$ perl ./last-sunday.pl 2023
2023/01/29
2023/02/26
2023/03/26
2023/04/30
2023/05/28
2023/06/25
2023/07/30
2023/08/27
2023/09/24
2023/10/29
2023/11/26
2023/12/31
``````

### Last Sunday in Julia

The Julia Dates module provides everything we need, including a `lastdayofmonth` method.

``````using Dates

function sundays(year, month)
month_end = Dates.lastdayofmonth(Dates.Date(year, month, 1))
weekday = Dates.dayofweek(month_end)
println(month_end - Dates.Day(weekday % 7))
end

year = parse( Int, ARGS[1])
for month in 1:12
sundays(year, month)
end
``````

Output:

``````\$ julia ./last-sunday.jl 2022
2022-01-30
2022-02-27
2022-03-27
2022-04-24
2022-05-29
2022-06-26
2022-07-31
2022-08-28
2022-09-25
2022-10-30
2022-11-27
2022-12-25
``````

### Last Sunday in Python

Python’s `datetime` module doesn’t have a `lastdayofmonth` method, but we can use the `timedelta(days = 1)` method to subtract one day from the first day of the next month. We only need a bit of simple arithmetic to find the next month.

``````from datetime import date,timedelta
import sys

def lastsundays (y):
for m in range(1,13):
if m == 12:
year = y + 1
month = 1
else:
year = y
month = m + 1

mthEnd = date(year, month, 1) - timedelta(days = 1)
weekDay = mthEnd.weekday()
lastSun = mthEnd - timedelta(days = (weekDay + 1) % 7)
print(lastSun)

if len(sys.argv) == 2:
year = int(sys.argv[1])
else:
year = 2022

lastsundays(year)
``````

Output:

``````\$ python3 ./last-sunday.py
2022-01-30
2022-02-27
2022-03-27
2022-04-24
2022-05-29
2022-06-26
2022-07-31
2022-08-28
2022-09-25
2022-10-30
2022-11-27
2022-12-25
``````

### Last Sunday in Ruby

The Ruby `date` class provides a `next_month` and a `prev_day` methods that we can chain to get the last day of the month (`lmd`) in just one code line. Thus, the Ruby solution is particularly concise.

``````require 'date'

year = ARGV.shift.to_i.nil? || 2022

for month in 1..12
lmd = Date.new(year, month, 1).next_month.prev_day
weekday = lmd.wday
puts lmd - (weekday % 7)
end
``````

Output:

``````2022-01-30
2022-02-27
2022-03-27
2022-04-24
2022-05-29
2022-06-26
2022-07-31
2022-08-28
2022-09-25
2022-10-30
2022-11-27
2022-12-25
``````

## Task 2: Perfect Totient Numbers

Output:

``````3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571
``````

Wikipedia explains us that, in number theory, Euler’s totient function counts the positive integers up to a given integer n that are relatively prime to n. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1. For example, there are 4 integers less than 10 that are prime relatively prime to 10: 1, 3, 7, 9. So, the totient of 10 is 4.

A perfect totient number is an integer that is equal to the sum of its iterated totients. That is, we apply the totient function to a number n, apply it again to the resulting totient, and so on, until the number 1 is reached, and add together the resulting sequence of numbers; if the sum equals n, then n is a perfect totient number.

For example, there are six positive integers less than 9 and relatively prime to it (1, 2, 4, 5, 7, 8), so the totient of 9 is 6; there are two numbers less than 6 and relatively prime to it (1, 5), so the totient of 6 is 2; and there is one number less than 2 and relatively prime to it (1), so the totient of 2 is 1; and 9 = 6 + 2 + 1, so 9 is a perfect totient number.

Once we’ve understood what a perfect totient number, it is quite easy to program a `is_perfect_totient` function that determines whether an input integer is a perfect totient. We need a `gcd` function to find out whether an integer is relatively prime to another. Some programming languages provide a built-in `gcd` function; for other languages, we’ll need to implement our own `gcd` function (see for example the Perl implementation below).

### Perfect Totient Numbers in Raku

Raku has a built-in infix gcd operator. So it is quite easy: in the `is-perfect-totient` subroutine, we simply compute the totient of the input number n (i.e. count the number positive integers up to n that are relatively prime to n), then iteratively compute the totient of the totient, and so on, until we reach 1. Finally, we compare the sum of all totients to the original input number.

#### Raw Unoptimized Version

This is our first Raku version.

``````# Unoptimized version, don't use it
my \$count = 0;
for 2..Inf -> \$n {
print "\$n " and \$count++ if is-perfect-totient \$n;
last if \$count >= 20;
}
say "";
sub is-perfect-totient (\$num) {
my \$n = \$num;
my \$sum = 0;
while \$n >= 1 {
\$n = (grep { \$n gcd \$_ == 1 }, 1..^\$n).elems;
\$sum += \$n;
}
return \$num == \$sum;
}
``````

This program displays the following output:

``````\$ raku ./perfect-totient.raku
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

The program becomes quite slow for the last perfect totient values (about 25 seconds to run). I tried some micro-optimizations, but without any significant improvement.

#### Caching the Totient Sums (Naive Version)

If you think about it, the above program computes the sum of the totients many times for the same number. We could store these values to avoid recomputing them. This strategy is called caching (or sometimes memoizing). We use the `@tot` array as a cache (or memo) to store the totient sums. When we want to compute the totient of a number, we first check if it is in the cache and use this value if such is the case, and we do the computation the hard way (with `gcd`) only if it is not in the cache.

This could lead to this program:

``````# Naive caching strategy
my \$count = 0;
my @tot = 0, 0;
for 2..Inf -> \$n {
print "\$n " and \$count++ if is-perfect-totient \$n;
last if \$count >= 20;
}
say "";
say "Time spent: ", now - INIT now;

sub is-perfect-totient (\$num) {
my \$n = \$num;
my \$sum = 0;
while \$n >= 1 {
if (defined @tot[\$n]) {
\$sum += @tot[\$n];
last;
} else {
\$n = (grep { \$n gcd \$_ == 1 }, 1..^\$n).elems;
\$sum += \$n;
}
}
@tot[\$num] = \$sum;
return \$num == \$sum;
}
``````

This program displays the following output:

``````\$ ./raku perfect-totient_cached_1.raku
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
Time spent: 15.32900533
``````

So we are now at 15 seconds. This is a significant improvement (although less than what I hoped).

#### Caching the Totient Sums (Improved Version)

We are testing every integer in ascending order. When we are testing one such new integer we know for sure that we haven’t computed its totient sum so far and need to compute it, and we also know for sure that we have already done the calculation for its totient number (provided we supply a first value). In other words, we no longer need the `while` loop, we can just compute the totient for the new input integer, and add to that the totient sum of the totient, which we are guaranteed to have in the cache. This leads to a significant code simplification of the `is-perfect-totient` subroutine:

``````# Improved caching strategy
my \$count = 0;
my @tot = 0, 0;
for 2..Inf -> \$n {
print "\$n " and \$count++ if is-perfect-totient \$n;
last if \$count >= 20;
}
say "";
say "Time spent: ", now - INIT now;

sub is-perfect-totient (\$num) {
my \$sum = (grep { \$num gcd \$_ == 1 }, 1..^\$num).elems;
\$sum += @tot[\$sum];
@tot[\$num] = \$sum;
return \$num == \$sum;
}
``````

This program displays the following output:

``````\$ raku ./perfect-totient_cached_2.raku
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
Time spent: 12.34103864
``````

The code simplification has also led to an additional performance improvement of about 20%.

### Perfect Totient Numbers in Perl

Our Perl implementation is really a port to Perl of the first Raku program above, with the only difference that we need to implement our own `gcd` subroutine, since two numbers are relatively prime (or coprime) if their greatest common divisor equals 1. For this, our `gcd` subroutine will use the so-called Euclidean algorithm, which is an improved variant of Euclid’s original method.

#### Raw Unoptimized Version

This is our first Perl version.

``````# Unoptimized version, don't use it
use strict;
use warnings;
use feature qw/say/;

sub gcd {
my (\$i, \$j) = sort { \$a <=> \$b } @_;
while (\$j) {
(\$i, \$j) = (\$j, \$i % \$j);
}
return \$i;
}
sub is_perfect_totient {
my \$num = shift;
my \$n = \$num;
my \$sum = 0;
while (\$n >= 1) {
\$n = scalar grep { gcd( \$n, \$_) == 1 } 1..\$n-1;
\$sum += \$n;
}
return \$num == \$sum;
}
my \$count = 0;
my \$n = 1;
while (\$count < 20) {
print "\$n " and \$count++ if is_perfect_totient \$n;
\$n++;
}
say "";
``````

This program displays the following output:

``````\$ perl  ./perfect-totient.pl
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

This program is even slower (39 seconds) than the first Raku version (25 seconds), presumably because of the pure Perl implementation of the `gcd` function. So, we will also use the caching strategy previously tested in Raku

#### Caching the Totient Sums

Here, we will go directly to the improved caching strategy used in the third Raku program because it makes the code simpler (and slightly faster).

``````# Optimized cached version
use strict;
use warnings;
use feature qw/say/;

my @tot = (0, 0);

sub gcd {
my (\$i, \$j) = sort { \$a <=> \$b } @_;
while (\$j) {
(\$i, \$j) = (\$j, \$i % \$j);
}
return \$i;
}

sub is_perfect_totient {
my \$num = shift;
my \$sum = scalar grep { gcd( \$num, \$_) == 1 } 1..\$num-1;
\$sum += \$tot[\$sum];
\$tot[\$num] = \$sum;
return \$num == \$sum;
}

my \$count = 0;
my \$n = 1;
while (\$count < 20) {
print "\$n " and \$count++ if is_perfect_totient \$n;
\$n++;
}
say "";
``````

Output:

``````\$ time perl perfect-totient_cached.pl
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571

real    0m20,371s
user    0m20,281s
sys     0m0,046s
``````

So, our caching program runs almost twice faster than our original Perl program.

### Perfect Totient Numbers in Julia

This is port to Julia of the Raku program above. Julia has a built-in gcd function that we put for good use.

``````function is_perfect_totient(num)
n = num
sum = 0
while n >= 1
n = length( filter((x) -> gcd(x, n) == 1, 1:n-1))
sum += n
end
return num == sum
end

count = 0
n = 1
while count < 20
if is_perfect_totient(n)
print("\$n ")
global count += 1
end
global n += 1;
end
``````

Output:

``````\$ julia ./perfect-totient.jl
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

This Julia implementation runs much faster (less than 4 seconds) than the Raku and Perl versions. There is probably no urgent need to try to use the caching strategy used for Raku and Perl, but let’s try. The cached version below runs about twice faster (less than 2 seconds):

``````cache = zeros(Int64, 1, 10000)

function is_perfect_totient(num)
tot = length( filter((x) -> gcd(x, n) == 1, 1:n-1))
sum = tot + cache[tot]
cache[num] = sum
return num == sum
end

count = 0
n = 2
while count < 20
if is_perfect_totient(n)
print("\$n ")
global count += 1
end
global n += 1;
end
``````

From now on, for other guest-languages, we will go directly for the improved cache strategy (faster and simpler code).

### Perfect Totient Numbers in C

C doesn’t have a built-in `gcd` function, so we implement our own.

``````#include <stdio.h>
#define MAX_VAL 50000

int cache[MAX_VAL];

int gcd(int i, int j) {
while (j != 0) {
int temp = i % j;
i = j;
j = temp;
}
return i;
}

int is_perfect_totient (int num) {
int tot = 0;
for (int i = 1; i < num; i++) {
if (gcd(num, i) == 1) {
tot++;
}
}
int sum = tot + cache[tot];
cache[num] = sum;
return num == sum;
}

int main() {
int j = 1;
int count = 0;
while (count < 20) {
if (is_perfect_totient(j)) {
printf("%d ", j);
count++;
}
j++;
}
printf("%s\n", " ");
}
``````

Output:

``````\$ time ./a.exe
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571

real    0m1,441s
user    0m1,374s
sys     0m0,015s
``````

### Perfect Totient Numbers in bc

In bc, which is really an arbitrary precision basic calculator with some programming features, we also need to implement our own `gcd` function.

``````define gcd (i, j) {
while(j != 0) {
k = j
j = i % j
i = k
}
return i
}

define is_perfect_totient (num) {
tot = 0
for (i = 1; i < num; i++) {
if (gcd(num, i) == 1) {
tot += 1
}
}
sum = tot + cache[tot]
cache[num] = sum
return num == sum
}

j = 1
count = 0
# we only go to 15 (not 20) because bc is very slow
while (count <= 15) {
if (is_perfect_totient(j)) {
print j, " "
count += 1
}
j += 1
}
print "\n"
quit
``````

Since bc is really slow, we display only the first 16 perfect totient numbers:

``````\$ time bc -q perfect-totient.bc
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199

real    0m35,553s
user    0m35,437s
sys     0m0,030s
``````

### Perfect Totient Numbers in awk

``````In awk also we need to implement our own `gcd` function.

function gcd (i, j) {
while(j != 0) {
k = j
j = i % j
i = k
}
return i
}
function is_perfect_totient (num) {
tot = 0
for (i = 1; i < num; i++) {
if (gcd(num, i) == 1) {
tot += 1
}
}
sum = tot + cache[tot]
cache[num] = sum
return num == sum
}
BEGIN {
j = 1
count = 0
while (count < 20) {
if (is_perfect_totient(j)) {
printf "%d ", j
count += 1
}
j += 1
}
print " "
}
``````

Output:

``````\$ time awk -f perfect-totient.awk
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 557

real    0m48,899s
user    0m48,656s
sys     0m0,046s
``````

### Perfect Totient Numbers in D

D has a built-in `gcd` function in the `std.numeric` module.

``````import std.stdio;
import std.numeric;

int[10000] cache;

bool is_perfect_totient(int num) {
int tot = 0;
for (int i = 1; i < num; i++) {
if (gcd(num, i) == 1) {
tot++;
}
}
int sum = tot + cache[tot];
cache[num] = sum;
return num == sum;
}

void main() {
int j = 1;
int count = 0;
while (count < 20) {
if (is_perfect_totient(j)) {
printf("%d ", j);
count++;
}
j++;
}
writeln(" ");
}
``````

Output:

``````3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

This ran in 1.34 seconds (but not the same hardware, so don’t compare with other timings).

### Perfect Totient Numbers in Ring

``````t_start = clock()
j = 1
count = 0
cache = list(10000)
while count < 14
if is_perfect_totient(j)
see "" + j + " "
count++
ok
j++
end
see nl
duration = (clock() - t_start)/clockspersecond()
see "" + duration + nl

func gcd (i, j)
while j != 0
k = i % j
i = j
j = k
end
return i

func is_perfect_totient (num)
tot = 0
for i = 1 to (num-1)
if gcd(num, i) = 1
tot++
ok
next
sum = tot + cache[tot+1]
cache[num+1] = sum
return num = sum
``````

Output:

``````\$ ring ./perfect-totient.ring
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
207.40
``````

This program ran in 207.40 seconds, so it isn’t fast. However, it is possible to compile Ring source code into binary executable files (apparently with an intermediate C file). This should presumably be much faster, but I wasn’t able to do this so far because of various environment problems.

### Perfect Totient Numbers in Python

Python has a `gcd` function in the `math` module.

``````import math

cache = [0] * 10000

def is_perfect_totient (n):
tot = 0
for i in range(1, n):
if (math.gcd(n, i) == 1):
tot += 1
``````

​ sum = tot + cache[tot] ​ cache[n] = sum ​ return n == sum

i = 1 ​ count = 0 ​ while count < 20: ​ if isperfecttotient(i): ​ print(i, end = ” “) ​ count += 1 ​ i += 1 ​ print(” “)

Output:

``````\$ time python3 ./perfect-totient.py
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571

real    0m4,832s
user    0m4,718s
sys     0m0,076s
``````

### Perfect Totient Numbers in Kotlin

In Kotlin, we had to implement our own `gcd` function.

``````val cache = Array(10000, {i-> 0})

fun gcd (m: Int, n: Int): Int {
var i = m
var j = n
while(j != 0) {
val k = j
j = i % j
i = k
}
return i
}

fun is_perfect_totient(n: Int): Boolean {
var tot = 0
for (i in 1..n-1) {
if (gcd(n, i) == 1) {
tot++
}
}
val sum = tot + cache[tot]
cache[n] = sum
return n == sum
}

fun main() {
var i = 0
var count = 0
while (count <= 20) {
if (is_perfect_totient(i)) {
print("\$i ")
count++
}
i++
}
println(" ")
}
``````

Output:

``````0 3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

This program ran in 2.5 seconds.

### Perfect Totient Numbers in Rust

The Rust`num::integer` library provides a `gcd` function. In my humble opinion, Rust is nevertheless a pain in the neck to use because of its ultra-strict type system. As an example, I could not use a simple integer (`i32`) as an array subscript, because Rust wants a `usize` type. That’s why I had to use expressions like `CACHE[n as usize]`. Similarly, Rust forced me to have my global cache array in uppercase. And, since it is a global variable, I had to wrap accesses to the cache in a `unsafe{]` block. I personally don’t think a programming language should get in the way of developers to such an extent. I really wasted quite a bit of time working around this straitjacket.

``````use num::integer::gcd;

static mut CACHE:[i32;10000] = [0; 10000];

fn is_perfect_totient(n: i32) -> bool {
let mut  tot = 0;
for i in 1..n {
if gcd(n, i) == 1 {
tot += 1
}
}
unsafe {
let sum = tot + CACHE[tot as usize];
CACHE[n as usize] = sum;
return n == sum;
}
}

fn main() {
let mut i = 1;
let mut count = 0;
while count < 20 {
if is_perfect_totient(i) {
print!("{} ", i);
count += 1;
}
i += 1;
}
println!("{}", " ")
}
``````

Ouput:

``````3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

### Perfect Totient Numbers in Java

Java has a `gcd` function bizarrely sitting in the `java.math.BigInteger` class. For a program performing heavy number crunching, I did not think it was reasonable to accept the performance penalty associated with big integers. So, I wrote my own `gcd` function.

``````public class PerfectTotient {

static int[] cache = new int[10000];

public static int gcd(int i, int j) {
while (j != 0) {
int temp = i % j;
i = j;
j = temp;
}
return i;
}
public static boolean isPerfectTotient(int n) {
int tot = 0;
for (int i = 1; i < n; i++) {
if (gcd(n, i) == 1) {
tot++;
}
}
int sum = tot + cache[tot];
cache[n] = sum;
return n == sum;
}

public static void main(String[] args) {
int i = 0;
int count = 0;
while (count < 20) {
if (isPerfectTotient(i)) {
System.out.printf("%d ", i);
count++;
}
i++;
}
System.out.printf("%s", "\n");
}
}
``````

Ouput:

``````0 3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

The compiled program ran in 1,23 second (not on the same hardware as most timings in this post).

### Perfect Totient Numbers in Nim

Nim has a `gcd` function in its `math` library.

``````import math

var cache: array[0..10000, int]

proc is_perfect_totient (n: int): bool =
var tot = 0
for i in 1..n-1:
if (gcd(n, i) == 1):
tot += 1
let sum = tot + cache[tot]
cache[n] = sum
return sum == n

var i = 1
var count = 0
while count < 20:
if is_perfect_totient(i):
stdout.write i, " "
count += 1
i += 1
echo ""
``````

Output:

``````3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

This program ran in 13 seconds.

### Perfect Totient Numbers in Go

No `gcd` in plementation in go, so we rolled out our own.

``````import "fmt"

var cache [10000]int

func gcd(i int, j int) int {
for j != 0 {
temp := i % j
i = j
j = temp
}
return i
}

func is_perfect_totient(n int) bool {
tot := 0
for i := 1; i < n; i++ {
if gcd(n, i) == 1 {
tot++
}
}
sum := tot + cache[tot]
cache[n] = sum
return n == sum
}

func main() {
i := 0
count := 0
for count <= 20 {
if is_perfect_totient(i) {
fmt.Printf("%d ", i)
count++
}
i++
}
fmt.Println("")
}
``````

Output:

``````0 3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

### Perfect Totient Numbers in JavaScript

``````var cache = new Array(10000)
cache[0] = 0

function gcd (i, j) {
while(j != 0) {
k = j
j = i % j
i = k
}
return i
}

function is_perfect_totient (n) {
let tot = 0
for (var i = 1; i < n; i++) {
if (gcd(n, i) == 1) {
tot++
}
}
sum = tot + cache[tot]
cache[n] = sum
return n == sum
}

let count = 0
let i = 1
while (count < 20) {
if (is_perfect_totient(i)) {
process.stdout.write(i + " ")

count++
}
i++
}
process.stdout.write("\n")
``````

Output:

``````3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

### Perfect Totient Numbers in Dart

Dart has a `gcd` method, which we will use.

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

var cache = List<int>.filled(10000, 0, growable: true);

void main() {
cache[0] = 0;
var count = 0;
var i = 1;
while (count < 20) {
if (is_perfect_totient(i)) {
stdout.write("\$i ");
count++;
}
i++;
}
print(" ");
}

bool is_perfect_totient(n) {
var tot = 0;
for (int i = 1; i < n; i++ ) {
if (i.gcd(n) == 1) {
tot++;
}
}
int sum = tot + cache[tot];
cache[n] = sum;
return n == sum;
}
``````

Output:

``````3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

### Perfect Totient Numbers in Ruby

Ruby has a `gcd` mehod, so we’ll use it.

``````\$cache = Array.new(10000, 0) # global variables require \$

def is_perfect_totient(n)
tot = 0
for i in 1..(n - 1)
if n.gcd(i) == 1
tot += 1
end
end
sum = tot + \$cache[tot]
\$cache[n] = sum;
return sum == n
end

i = 1
count = 0
while count < 20
if is_perfect_totient(i)
printf("%d ", i)
count += 1
end
i += 1
end
print("\n")
``````

Output:

``````3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

### Perfect Totient Numbers in Scala

Scala has a `gcd` function, but only for big integers (probably because Scala relies on Java, which has the same property). For a program performing heavy number crunching, I did not think it was reasonable to accept the performance penalty associated with big integers. So, I wrote my own `gcd` function for plain integers.

``````object PerfectTotient extends App {

var cache = new Array[Int](10000)

def gcd(a: Int, b: Int): Int = {
var (i, j) = (a, b)
while (j > 0) {
var t = i
i = j
j = t % j
}
return i
}

def is_perfect_totient(n: Int): Boolean = {
var tot = 0
for (i <- 1 to (n - 1)) {
if (gcd(n, i) == 1) {
tot += 1
}
}
val sum = tot + cache(tot)
cache(n) = sum
return n == sum
}

var i = 1
var count = 0
while (count < 20) {
if (is_perfect_totient(i)) {
count += 1
printf("%d ", i)
}
i += 1
}
println("")
}
``````

Output:

``````3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
``````

### Perfect Totient Numbers in Tcl

Tcl doesn’t have a built-in `gcd` function, so I wrote one.

``````array set cache {}

set cache(0) 0

proc gcd {i j} {
while {\$j != 0} {
set t [expr {\$i % \$j}]
set i \$j
set j \$t
}
return \$i
}

proc is_perfect_totient {n} {
global cache
set tot 0
for {set i 1} {\$i < \$n} {incr i} {
if [ expr [gcd \$i \$n] == 1 ] {
incr tot
}
}
set sum [expr \$tot + \$cache(\$tot)]
set cache(\$n) \$sum
return [ expr \$n == \$sum ? 1 : 0]
}

set i 1
set count 0
while { \$count < 20 } {
if [ is_perfect_totient \$i ] {
puts -nonewline  "\${i} "
incr count
}
incr i
}
puts ""
``````

As a fully interpreted language, Tcl is quite slow, as it can be seen in the following output:

``````\$ time tclsh ./perfect-totient.tcl
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571

real    1m18,058s
user    1m17,593s
sys     0m0,046s
``````

## 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 7, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.

## Perl Weekly Challenge 174: Disarium Numbers in dc

This blog is an answer to the first task (Disarium Numbers) of the Week 174 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Originally, the Perl Weekly Challenge called for solutions in Perl and Raku (also known as Perl 6 at the time). But, very soon, people started to provide solutions in other “guest” languages. See for example my blog post providing solutions to the task described below in about 18 different guest languages.

One of the languages I tried for the first time last week with Sylvester’s sequence is dc, and it turned out to be much more difficult and challenging than I initially thought. One of the problems is that there is only very limited documentation on this old programming language. So I thought it might be useful to describe in some details how I solved it. I provided detailed explanations in this other blog post. I’ll now do the same with the disarium number task of this week, which is a bit more complicated.

## The Disarium Number Task of Perl Weekly Challenge 174

Write a script to generate first 19 Disarium Numbers.

A disarium number is an integer where the sum of each digit raised to the power of its position in the number, is equal to the number.

For example,

``````518 is a disarium number as (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518
``````

## Disarium Numbers in Some Other Languages

The dc language is difficult and poorly documented. Before we get to it, I want to illustrate the algorithm I’ll implement with some other more traditional languages.

You can find solutions to this problem in 17 programming languages in this other blog post. I’ll show two of them below.

### Disarium Numbers in Raku

``````sub is-disarium(\$num) {
my @digits = \$num.comb;
my \$sum = [+] map { \$^b ** (\$^a + 1) }, @digits.kv;
return \$num == \$sum;
}
my \$count = 0;
my \$i = 0;
while \$count < 19 {
++\$count and say \$i if is-disarium(\$i);
\$i++;
# say "i: \$i";
}
``````

This program displays the following output:

``````0
1
2
3
4
5
6
7
8
9
89
135
175
518
598
1306
1676
2427
2646798
``````

### Disarium Numbers in Perl

``````use strict;
use warnings;
use feature "say";

sub is_disarium {
my \$num = shift;
my @digits = split '', \$num;
my \$i = 1;
my \$sum = 0;
\$sum += \$_ for map {  \$_ ** \$i++ } @digits;
return \$num == \$sum;
}
my \$i = 0;
my \$count = 0;
while (\$count < 19) {
say \$i and \$count++ if is_disarium \$i;
\$i++;
}
``````

This Perl program displays the same output as the Raku program above.

### Disarium program in awk

The dc language doesn’t have the powerful string functions of Raku, Perl, or Julia. Let me provide here an awk implementation, because awk also doesn’t have these string functions. In the `while` loop of the `is_disarium` function, we use the integer division and modulo operators to get each digit of the input integer in turn. We’ll have to do something similar in dc.

``````function is_disarium(num) {
n = num
sum = 0
len = length(n)
while (n > 0) {
sum += (n % 10) ^ len
n = int(n/10)
len--
}
return (sum == num)
}

BEGIN {
count = 0
i = 0
while (count < 19) {
if (is_disarium(i)) {
printf("%d\n", i)
count++
}
i++
}
}
``````

This awk program displays the same output as the Raku program above.

## Introducing dc

According to Wikipedia), dc (desk calculator) is a cross-platform reverse-Polish calculator which supports arbitrary-precision arithmetic. Written by Lorinda Cherry and Robert Morris at Bell Labs, it is one of the oldest Unix utilities, preceding even the invention of the C programming language. dc is docucumented in section 2 of the first ediion of Bell Labs’s Unix Programmer’s Manual published on Nov 3, 1971, so dc was probably written in 1970 or latest in 1971. Like other utilities of that vintage, it has a powerful set of features but terse syntax. Traditionally, the bc calculator program (with infix notation) was implemented on top of dc.

dc is the oldest surviving Unix language program. When its home Bell Labs received a PDP-11, dc—written in B—was the first language to run on the new computer, even before an assembler.

It uses reverse Polish notation (RPN) which was also used around the same time by Hewlett-Packard pocket calculators. Actually, the main reason I am interested with dc (despite its awful worse-than-assembler syntax) is that this is essentially the type of language with which I first learned to program back in the mid-1970s with a programmable pocket calculator.

RPN is a postfix notation in which you first specify the operands and then the operator.

``````\$ echo '5 6 + p' | dc
11
``````

As you can see, we first input the two operands (5 and 6), and then the `+` operator, and finally the `p` operator to print out the result of the addition. Prefix your number with an underscore if you want to specify a negative number (e.g. `_5` for -5)

The spaces are not needed (except between 5 and 6) but improve readability. We could have written it this way:

``````\$ echo '5 6+p' | dc
11
``````

dc can also be used in interactive mode:

``````\$ dc
5 6
+
p
11
q
``````

or:

``````\$ dc
5 6 + p q
11
``````

This can be quite convenient to test chunks of code and we will use that feature.

We can also use the `-e` (or `--expression`) command-line option to specify a simple program between single quotes:

``````\$ dc -e '5 6 + p'
11
``````

dc uses a stack to perform its operations. Stacks are very commonly used data structure in computer science. A stack is a last in / first out data structure. Think of piled-up plates. When you put a clean plate on the stack, you usually put it on top; when you take one out, you also take it from the top. So, the first plate that you take out is the last one that you added. The dc stack implements the same idea: the first piece of data you take out is the last one you added. Adding a new piece of data onto the stack is usually called a push operation, and taking out one piece of data from the stack is called a pop operation.

The various commands above can be understood as follows:

``````\$ dc
5   # push 5 to stack
6   # push 6 to stack
f   # display stack (displays 6 and 5). Useful for debugging
6
5
+   # pop two items from stack, add them and push result to stack
p   # print top item of the stack (prints 11)
11
q   # quit
``````

Note that the `#` sign indicates the beginning of a comment (the rest of the line is ignored).

For full details on the dc syntax, please consult the dc GNU manual. We will describe here only the most common commands, those that we are likely to use for our program. The best tutorial I have found on dc is the Wikipedia dc page).

### Printing Commands

``````p   Prints the value on the top of the stack, not altering the stack.
n   Prints the value on the top of the stack, popping it off
f   Prints the entire contents of the stack without altering anything.
``````

### Stack Control

``````c   Clears the stack, rendering it empty
d   duplicate the value on top of the stack
r   Reverses the order of (swaps) the top two values on the stack.
``````

### Registers

dc provides at least 256 memory registers, each named by a single character. You can store a number in a register and retrieve it later.

``````sr  Pops the value off the top of the stack, stores it in register r.
lr  Copies the value in register r, and pushes it onto the stack.
This does not alter the contents of r.
``````

Each register also contains its own stack. The current register value is the top of the register’s stack. If you want to use a register r as a stack, use `Sr` (with uppercase S) to push the top of stack value to r, and `Lr` (with uppercase L) to pop a value from r and push it on the main stack. We will not use the stack features of registers in this blog post.

### Arithmetic

``````+   Pops two values off the stack, adds them, and pushes the result.
-   Pops two values, subtracts the first one popped from the second
one popped, and pushes the result.
*   Pops two values, multiplies them, and pushes the result.
/   Pops two values, divides the second one popped from the first
one popped, and pushes the result. The number of fraction digits
is specified by the precision value. Default is integer division.
%   Pops two values, computes the remainder of the division that
the `/` command would do, and pushes that.
^   Pops two values and exponentiates, using the first value popped
as the exponent and the second popped as the base.
``````

### Strings

dc can operate on strings as well as on numbers. The only things you can do with strings are print them and execute them as macros (which means that the contents of the string are processed as dc commands).

For example, to print twice a string in the interactive mode:

``````\$ dc
[Hello wolrd!]p
Hello wolrd!
p
Hello wolrd
``````

or:

``````\$ dc
[Hello wolrd!]pp
Hello wolrd!
Hello wolrd!
``````

Now, let’s try to write a simple string containing dc statements to increment by 2 the value on the stack, and to run it as a macro (using the `x` command):

``````\$ dc
20          # pushes 20 to stack
[2 + p] x   # [2 + p] is a string that means "push 2 to stack,
# add the two top items of the stack and print result.
# x runs the [2 + p] sting as a macro
22
q
``````

Both registers and the stack can hold strings, and dc always knows whether any given object is a string or a number.

``````[ch] Makes a string containing "ch" and pushes it on the stack.
x   Pops the value from the top of the stack and executes it as a macro
>r  Pops two values off the stack and compares them assuming they are
numbers, executing the contents of register r as a macro if the
original top-of-stack is greater
<r  Similar but invokes the macro if the original top-of-stack is less
=r  Similar but invokes the macro if the original top-of-stack is equal
``````

### Macros

Macros are then implemented by allowing registers and stack entries to be strings as well as numbers. A string can be printed, but it can also be executed (i.e. processed as a sequence of dc commands). For instance, we can store a macro to add 3 and then multiply by 2 into register m:

``````[3 + 2 *] sm
``````

and then (using the `x` command which executes the top of the stack) we can use it like this:

``````3 lm x p
``````

This displays the following:

``````\$ dc -e '[3 + 2 *] sm 3 lm x p'
12
``````

For better understanding, this is a detailed account of what’s going on:

``````[    # start of macro definition
3  # push 3 to stack
+  # pop 2 values off the stack, add them and store result on stack
2  # push 2 on stack
*  # pop 2 values off the stack, multiply them, store result on stack
]    # end of macro definition
sm   # store the macro just defined in register m
3    # push 3 on stack
lm   # copy value in register m (the macro) onto the stack
x    # run the macro
p    # print the result (top of the stack)
``````

### Conditionals and Loops in dc

The `=`, `>`, `!>`, `<`, `!<`, `!=` conditionals execute the subsequent macro when the two top values of the stack are equal, larger than, not larger than, etc. For example, in:

``````\$ dc -e '[[smaller than]p] sm 6 5 <m'
smaller than
``````

the macro stored in `m` runs (and prints “smaller than”) because 5 is smaller than 6. The `<` pops 5 and then 6 from the stack and runs the macro in register `m` because the first popped value (5) is smaller than the second popped value.

Let’s look at a simple countdown in this page in the Bash Hackers Wiki:

``````dc << EOF
[ li       # put our index i on the stack
p        # print it, to see what's going on
1 -      # we decrement the index by one
si       # store decremented index (i=i-1)
0 li >L   # if i > 0 then execute recursively L
] sL       # store our macro with the name L
10 si      # let's give to our index the value 10
lLx        # and start our loop
EOF

10
9
8
[ Lines omitted for brevity]
2
1
``````

Basically, the macro is called a first time, and then calls itself recursively so long as the condition is satisfied.

## Disarium Numbers in dc

Remember that we want to write something similar to the `is_disarium` function of our above-described awk program:

``````function is_disarium(num) {
n = num
sum = 0
len = length(n)
while (n > 0) {
sum += (n % 10) ^ len
n = int(n/10)
len--
}
return (sum == num)
}
``````

Our program will be composed essentially of four macros calling themselves or each other, and just a few additional code lines to start the whole process.

### The Length Macro

The above `is_disarium` function uses the awk built-in `length()` function. There is no such built-in function in dc. So our first task will be to write our own length macro.

The way this macro will work is that we’re going to repeatedly divide (integer division) the input number by 10, until we get to 0. At each step through the process, we increment the length (register l) by one.

The length macro itself is stored in the L register, and the length “variable” in register l.

``````[10      # pushes 10 to stack
/       # divides input by 10 and stores result on stack
ll      # pushes length on stack
1+      # adds one to stack (length)
# p     # prints intermediate length (for debugging)
sl      # saves length to register l
d       # duplicates value (number) on top of stack
0       # pushes 0 to stack
<Lx     # executes recursively length macro (L) if number > 0
] sL     # end of macro, stores it in L

889 sn   # stores some input number in n
ln       # pushes number to stack
0sl      # stores 0 in register l (length)
lLx      # runs the macro once to start the loop
llp      # prints length final value
``````

The last five lines in the code above (after the blank line) are not part of the macro, they are just some code to set up the environment before calling the macro: start with an input number (889 in the above example), initialize the length (register l) to 0, invokes the macro (stored in register L), and prints the length.

With an input number of 889, this program correctly prints out 3.

### The Disarium Macro

This macro is more or less equivalent to the `is_disarium` function’s `while` loop of the awk program:

``````while (n > 0) {
sum += (n % 10) ^ len
n = int(n/10)
len--
}
``````

The disarium macro computes the number modulo 10, then computes the result to the length power, adds the obtained value to the sum so far; it also divides the number by 10 (integer division) and decrements the length by 1. At the end, it calls itself recursively if the resulting number is larger than 0.

The disarium macro is stored in register D. The sum is stored in register s, the length in register l, and the input number in register n.

``````[d      # duplicates value (number) on top of stack
10      # pushes 10 to stack
%       # pushes (number % 10) to stack
ll      # pushes length to stack
^       # computes (n % 10) ^ len
ls      # pushes sum to stack
+ss     # computes new sum and stores it in s
10/     # integer division number / 10
ll      # pushes length on stack
1-      # subtract 1 froml length
sl      # stores new length in l
d       # duplicates value (number) on top of stack
0       # pushes 0 to stack
<Dx     # executes recursively disarium macro (D) if number > 0
] sD    # stores disarium macro in D

88 sn   # stores number in n
ln      # pushes number to stack
0sl     # stores 0 in register l (length)
lLx     # runs the length macro
0ss     # initializes sum to 0
cln     # clear stack and pushes number onto it
lDx     # runs the Disarium macro
lsln    # pushes sum and number
f       # display stack (sum and number)
``````

The 10 last code lines (after the blank line) are not part of the macro, but are needed to make a full dc program that can be tested independently (well you’ll also need the length macro described above). They initialize the input number to 88, the sum to 0, and the length to 0. Then we run the length macro (stored in L) and the disarium macro. At the end, we push the sum and the input number to the stack and can verify whether they are equal (in which case the input number is a disarium number) or not. With the input value of 88, the program displays:

``````88
72
0
``````

The input number (88) and the sum (72 = 8 * 8 + 8) are not equal, so 88 is not a disarium number.

If we change the input number to 89, we get the following output:

``````89
89
0
``````

The input number (89) and the sum (89 = 9 * 9 + 8) are equal, so 89 is a disarium number.

### The Iteration Macro

We need to iterate over the subsequent integers and, for each of them, call the length macro and then the disarium macro to find out whether it is a disarium number.

The macro stores the current iteration variable into the number register (this is the number we will test), initializes length to 0, runs the length macro, initialize sum to 0 and runs the disarium macro once. Then it pushes sum and number to stack and compares them. If they are equal (input number is a disarium number), it runs the printing macro (see below). Finally, it compares the disarium number with 18, and calls itself recursively if the counter is smaller than 18.

The iteration macro is stored in the I (capital i) register. The sum is stored in register s, the length in register l, the input number in register n, the iteration variable in register i, and the disarium number counter in register c.

``````[li sn  # Stores iteration variable in number register
ln      # pushes number to stack
0sl     # stores 0 in register l (length)
lLx     # runs the length macro
0ss     # inititialize sum to 0
cln     # clear stack and pushes number onto it
lDx     # runs the Disarium macro once
lsln    # pushes sum and number
=P      # runs the printing macro if numbers are equal
1+si    # increments iteration variable
lc18    # pushes counter and 18 on stack
>Ix     # runs recursively iteration macro if counter < 18
] sI    # end of iteration macro, stores it in I
``````

We cannot run this macro at this point, because we need a small additional macro, the printing macro.

### The Printing and Counting Macro

I’ve previously called it “printing macro” for the sake of brevity, but it is really a printing and counting macro. This macro runs only when input number and the computed sum are equal (i.e. when we have a disarium number). In that case, we need to do two things: print out the disarium number and increment by 1 the disarium number counter (so that we know when to stop the iteration macro).

The printing and counting macro is stored in the P register. The disarium number counter is stored in the c register, and the input number in register n.

``````[lc1+sc # increments disarium number counter
lnp     # print number
]sP     # Stores printing macro in P
``````

### The Final Disarium Number Program in dc

We can now put together all the pieces seen so far.

The macros are stored in upper-case letter registers:

• L: length of input number macro

• D: Disarium macro

• I: Iteration macro

• P: Printing and counting macro

The “variables” are stored in lower-case letter registers:

• n: Input number

• c: Disarium number counter

• l: Length of input number

• s: Sum

• i: Iteration variable

This is the full dc program:

``````# Macro for computing the input number length
[10      # pushes 10 to stack
/       # divides input by 10 and stores result on stack
ll      # push length on stack
1+      # add one to stack (length)
sl      # saves length to register l
d       # duplicates value (number) on top of stack
0       # pushes 0 to stack
<Lx     # executes recursively length macro (L) if number > 0
] sL     # end of macro, store it in L

# Disarium macro
[d      # duplicates value (number) on top of stack
10      # pushes 10 to stack
%       # pushes (number % 10) to stack
ll      # pushes length to stack
^       # computes (n % 10) ^ len
ls      # pushes sum to stack
+ss     # computes new sum and stores it in s
10/     # integer division number / 10
ll      # pushes length on stack
1-      # subtract 1 froml length
sl      # stores new length in l
d       # duplicates value (number) on top of stack
0       # pushes 0 to stack
<Dx     # executes recursively disarium macro (D) if number > 0
] sD    # stores disarium macro in D

# Printing and counting macro
[lc1+sc # increments disarium number counter
lnp     # print number
]sP     # Stores printing macro in P

# Iteration macro
[li sn  # Stores iteration variable in number register
ln      # pushes number to stack
0sl     # stores 0 in register l (length)
lLx     # runs the length macro
0ss     # inititialize sum to 0
cln     # clear stack and pushes number onto it
lDx     # runs the Disarium macro once
lsln    # pushes sum and number
=P      # runs the printing macro if numbers are equal
1+si    # increments iteration variable
lc18    # pushes counter and 18 on stack
>Ix     # runs recursively iteration macro counter < 18
] sI    # end of iteration macro, stores it in I

# Main
0si     # Initialize iteration variable
0sc     # Initialize disarium numbers counter
lIx     # running iteration macro the first time
``````

As you can see, the program consists of the four macros defined previously, plus just 3 code lines (the “Main” part) to initialize the iteration variable, initialize the disarium number counter and launch the iteration macro.

This program displays the following output:

``````\$ dc ./disarium.dc
0
1
2
3
4
5
6
7
8
9
89
135
175
518
598
1306
1676
2427
``````

But, of course, formatting the program with abundant spaces and comments as above is way too easy. Real programmers will prefer this one-liner version (spread over two lines for formatting reasons):

``````\$ dc -e '[10/ll1+sld0<Lx]sL[d10%ll^ls+ss10/ll1-sld0<Dx]sD[lc1+sc
lnp]sP[lisnln0sllLx0ssclnlDxlsln=Pli1+silc18>Ix]sI0si0sclIx'
0
1
2
3
[Lines omitted for brevity
598
1306
1676
2427
``````

## 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 July 31, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.

## Perl Weekly Challenge 174: Disarium Numbers and Permutation Rankings

These are some answers to the Week 174 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 July 24, 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.

Write a script to generate first 19 Disarium Numbers.

A disarium number is an integer where the sum of each digit raised to the power of its position in the number, is equal to the number.

For example,

``````518 is a disarium number as (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518
``````

In Raku and Perl, we’ll implicitly convert the input number into a string of characters (`@digits`), split it into an array of characters, and then implicitly convert each character into a digit. In some other languages such as awk, bc, or C, such implicit conversion don’t happen or are tedious, and we will use mathematical computations to get the individual digits.

### Disarium Numbers in Raku

This is quite straight forward. We have a `is-disarium` subroutine which returns a True value is the described sum is equal to the input value, and False otherwise. Then we use it to test each subsequent integer from 0 on and print out the number if it is a disarium number. We stop when we reach 19 disarium numbers.

``````sub is-disarium(\$num) {
my @digits = \$num.comb;
my \$sum = [+] map { \$^b ** (\$^a + 1) }, @digits.kv;
return \$num == \$sum;
}
my \$count = 0;
my \$i = 0;
while \$count < 19 {
++\$count and say \$i if is-disarium(\$i);
\$i++;
# say "i: \$i";
}
``````

This program displays the following output:

``````0
1
2
3
4
5
6
7
8
9
89
135
175
518
598
1306
1676
2427
2646798
``````

This program took 0.4 second to find the first 18 disarium numbers, and then more than 4 minutes to find the 19th one. I have to confess that, for years, I have been too lazy to upgrade my Rakudo installation, which dates from 2019. This time, I decided it was high time to upgrade it and installed version 2022.06 to see what happens.

The good news is that, with this new version, the program ran in about 45 seconds. More than five times faster, that’s a rather impressive improvement. The bad news, though, is that it’s still very slow. The equivalent Perl and Python programs (see below) both took slightly less than 10 seconds, the Julia implementation ran in 3 seconds, and the C program completed in less than half a second. There is definitely a large opportunity for performance improvement. I love Raku, but I must admit that, in terms or performance, it is currently not good at intensive number crunching.

### Disarium Numbers in Perl

This is a port to Perl of the Raku program just above, with a `is_disarium` subroutine to find is the input integer is a disarium number.

``````use strict;
use warnings;
use feature "say";

sub is_disarium {
my \$num = shift;
my @digits = split '', \$num;
my \$i = 1;
my \$sum = 0;
\$sum += \$_ for map {  \$_ ** \$i++ } @digits;
return \$num == \$sum;
}
my \$i = 0;
my \$count = 0;
while (\$count < 19) {
say \$i and \$count++ if is_disarium \$i;
\$i++;
}
``````

This program displays the following output:

``````\$ time perl ./disarium.pl

0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798

real    0m9,781s
user    0m9,625s
sys     0m0,046s
``````

### Disarium Numbers in Julia

Julia has the built-in `digits` function, which produces a list of digits of the input number (in the wrong order for our purpose), and `enumerate` iterator, which yields a list of indexes and values. These functions make the `is_disarium` function very simple (it could easily be written in one single code line).

``````function is_disarium(n)
s = sum(i ^ p for (p, i) in enumerate(reverse(digits(n))))
return s == n
end

count = 0
i = 0
while count < 19
if is_disarium(i)
println(i)
global count += 1
end
global i += 1
end
``````

Output:

``````julia ./disarium.jl
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798
``````

### Disarium Numbers in awk

The awk language doesn’t have the powerful string functions of Raku, Perl, or Julia. In the `while` loop of the `is_disarium` function, we use the integer division and modulo operators to get each digit of the input integer in turn.

``````function is_disarium(num) {
n = num
sum = 0
len = length(n)
while (n > 0) {
sum += (n % 10) ^ len
n = int(n/10)
len--
}
return (sum == num)
}

BEGIN {
count = 0
i = 0
while (count < 19) {
if (is_disarium(i)) {
printf("%d\n", i)
count++
}
i++
}
}
``````

Output:

``````\$ awk -f ./disarium.awk
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798
``````

### Disarium Numbers in bc

This program is very similar to the awk program just above, with the same method to access the individual digits.

``````define is_disarium (num) {
n = num
sum = 0
len = length(n)
while (n > 0) {
sum += (n % 10) ^ len
n = n/10
len -= 1
}
return (sum == num)
}

count = 0
i = 0
while (count < 19) {
if (is_disarium(i)) {
print i, "\n"
count += 1
}
i += 1
}
quit
``````

Output:

``````\$ bc  ./disarium.bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798
``````

### Disarium Numbers in dc

The problem can be solved with a dc one-liner (spread over two lines for formatting reasons):

``````\$ dc -e '[10/ll1+sld0<Lx] sL [d10%ll^ls+ss10/ll1-sld0<Dx] sD [lc1+sc
lnp] sP [lisnln0sllLx0ssclnlDxlsln=Pli1+silc18>Ix] sI0si0sclIx'
0
1
2
3
4
5
6
7
8
9
89
135
175
518
598
1306
1676
2427
``````

Note that I only printed 18 numbers because this is getting really slow.

This is not a golf attempt: I could have removed a few spaces if I had wanted to golf it.

But I must admit dc scripts are not easy to read. This is now a much more readable version of the same solution:

``````# Macro for computing the input number length
[10      # pushes 10 to stack
/       # divides input by 10 and stores result on stack
ll      # push length on stack
1+      # add one to stack (length)
# p     # prints intermediate length (for debugging)
sl      # saves length to register l
d       # duplicates value (number) on top of stack
0       # pushes 0 to stack
<Lx     # executes length macro (L) if number > 0
] sL     # end of length macro, store it in L

# is Disarium macro
[d      # duplicates value (number) on top of stack
10      # pushes 10 to stack
%       # pushes (number % 10) to stack
ll      # pushes length to stack
^       # computes (n % 10) ^ len
ls      # pushes sum to stack
+ss     # computes new sum and stores it in s
10/     # integer division number / 10
ll      # pushes length on stack
1-      # subtract 1 froml length
sl      # stores new length in l
d       # duplicates value (number) on top of stack
0       # pushes 0 to stack
<Dx     # executes recursively disarium macro (D) if number > 0
] sD    # stores disarium macro in D

# Printing and counting macro
[lc1+sc # increments disarium number counter
lnp     # print number
]sP # Stores printing macro in P

# Iteration macro
[li sn  # Stores iteration variable in number register
ln      # pushes number to stack
0sl     # stores 0 in register l (length)
lLx     # runs the length macro
0ss     # inititialize sum to 0
cln     # clear stack and pushes number onto it
# llp   # print the length
lDx     # runs the Disarium macro once
lsln    # pushes sum and number
=P      # runs the printing macro if numbers are equal
1+si    # increments iteration variable
lc18    # pushes counter and 18 on stack
>Ix     # runs recursively iteration macro if counter < 18
] sI    # end of iteration macro, stores it in I

# Main
0si     # Initiate iteration variable
0sc     # Initiate disarium numbers counter
lIx     # running iteration macro the first time
``````

Output:

``````\$ dc disarium.dc
0
1
2
3
[Lines omitted for brevity]
1306
1676
2427
``````

Understanding the solution in details would require a lot more explanations than what I can provide here. If you want to understand better how this program works and, more broadly, how the dc syntax works, you are kindly invited to read this other blog post where I describe the solution in detail.

### Disarium Numbers in C

The C programming language doesn’t have a standard exponentiation operator. So I wrote a `power` function to perform exponentiation of individual digits. There is also no direct way to find the number of digits of an integer. So, I used `floor(log10(n)) + 1` to find the size of an integer `n`, except that it would fail for an input of 0, so I used this method only for integers larger than 9.

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

int power (int base, int exponent) {
int result = 1;
for (int i = 1; i <= exponent; i++) {
result *= base;
}
return result;
}

int is_disarium (int num) {
int n = num;
int sum = 0;
int len = n <= 9 ? 1 : floor(log10(n)) + 1;
while (n > 0) {
sum += power(n % 10, len);
n /= 10;
len--;
}

return num == sum;
}

int main() {
int count = 0;
int i = 0;
while (count < 19) {
if (is_disarium(i)) {
printf("%d\n", i);
count++;
}
i++;
}
}
``````

Output:

``````\$ time ./a.out
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798

real    0m0,475s
user    0m0,280s
sys     0m0,015s
``````

### Disarium Numbers in Python

Also using the integer division and modulo operators to get each digit of the input integer.

``````def is_disarium(num):
n = num
size = len(str(n))
sum = 0
while n > 0:
sum += (n % 10) ** size
n //= 10
size -= 1
return sum == num

i = 0
count = 0
while count < 19:
if is_disarium(i):
print(i)
count += 1
i += 1
``````

Output:

``````\$ python3 disarium.py
0
1
2
3
[Lines omitted for brevity]
1306
1676
2427
2646798
``````

### Disarium Numbers in Ruby

``````def is_disarium(num)
n = num.to_s
sum = 0
for i in 1..(n.length)
sum += n[i-1].to_i**i
end
return sum == num
end

i = 0
count = 0
while count < 19
if is_disarium(i)
printf("%d ", i)
count += 1
end
i += 1
end
print("\n")
``````

From now on, our programs will display the disarium numbers on one line to save space:

``````0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in Kotlin

Kotlin has a `pow` function for exponentiation, but it works with `Double` and `Float` leading to numerous time-consuming difficulties. I ended up writing my own `power` functions for integers.

``````fun power(n: Int, exp: Int): Int {
return when {
exp > 1 -> n * power(n, exp-1)
exp == 1 -> n
else -> 1
}
}
fun is_disarium(num: Int): Boolean {
val n = num.toString()
var sum = 0
for (i in 1..n.length) {
sum += power (n[i-1] - '0', i)
}
return sum == num
}
fun main() {
var i = 0
var count = 0
while (count < 19) {
if (is_disarium(i)) {
print("\$i ")
count++
}
i++
}
println("")
}
``````

Output:

``````0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in Rust

I don’t really like Rust because, in my humble opinion, its type system is really an obstructive straitjacket and gets in the way of doing simple things. Just like in Kotlin, I ended up writing my own `power` functions for exponentiating integers.

``````fn power(n: i32, exp: i32) -> i32 {
let mut result = 1;
for _i in 0..exp {
result *= n;
}
return result;
}
fn is_disarium(num: i32) -> bool {
let mut n = num;
let mut sum = 0;
let mut i = 1;
let len = num.to_string().len();
while n > 0 {
sum += power(n % 10, len as i32 - i + 1);
n /= 10;
i += 1
}
return sum == num;
}
fn main() {
let mut i = 0;
let mut count = 0;
while count <= 18 {
if is_disarium(i) {
print!("{} ", i);
count += 1;
}
i += 1;
}
println!("{}", " ")
}
``````

Output:

``````0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in Java

``````import java.lang.Math;

public class DisariumNumbers {
public static boolean is_disarium(int num) {
int n = num;
int len = Integer.toString(n).length();
int sum = 0;
int i = 1;
while (n > 0) {
sum += Math.pow(n % 10, len - i + 1);
n /= 10;
i ++;
}
return sum  == num;
}

public static void main(String[] args) {
int i = 0;
int count = 0;
while (count <= 18) {
if (is_disarium(i)) {
System.out.printf("%d ", i);
count++;
}
i++;
}
System.out.printf("%s", "\n");
}
}
``````

Output:

``````0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in Scala

``````object Disarium extends App {
def power(base: Int, exp: Int): Int = {
var result = 1
for (i <- 1 to exp) {
result *= base
}
return result
}
def is_disarium(num: Int): Boolean = {
val digits = num.toString.split("")
var sum = 0
for (i <- 0 to (digits.size - 1)) {
sum += power(digits(i).toInt, i + 1)
}
return num == sum
}
var i = 0
var count = 0
while (count < 19) {
if (is_disarium(i)) {
count += 1
printf("%d ", i)
}
i += 1
}
println("")
}
``````

Output:

``````0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in Ring

``````i = 0
count = 0
while count < 19
if is_disarium(i)
see "" + i + " "
count++
ok
i++
end
see nl

func pow (base, exp)
result = 1
for i = 0 to exp - 1
result *= base
next
return result

func is_disarium (num)
n = "" + num
sum = 0
for i = 1 to len(n)
sum += pow (n[i] % 10, i)
next
return sum = num
``````

Output:

``````\$ ring ./disarium.ring
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in Nim

``````import strutils
import math

proc is_disarium(num: int): bool =
let n = intToStr(num)
var sum = 0
for i in 0..len(n)-1:
sum += int((int(n[i])-48) ^ (i+1))
return sum == num

var i = 0
var count = 0
while count < 19:
if is_disarium(i):
stdout.write i, " "
count += 1
i += 1
echo ""
``````

Output:

0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798

### Disarium Numbers in Go

``````package main

import (
"fmt"
"math"
"strconv"
)

func is_disarium(num int) bool {
n := num
i := 0
sum := 0
l := len(strconv.Itoa(n))
for n > 0 {
sum += int(math.Pow(float64(n%10), float64(l-i)))
n /= 10
i++
}
return sum == num
}
func main() {
i := 0
count := 0
for count < 19 {
if is_disarium(i) {
fmt.Printf("%d ", i)
count++
}
i++
}
fmt.Println("")
}
``````

Output:

``````0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in Tcl

I used to be a fan of Tcl some 25 to 30 years ago, not that I really loved Tcl itself, but because it came usually bundled with the Tk graphical toolkit, and I really loved Tk, which made fairly easy the design and implementation of graphical interfaces. But I wasn’t really impressed at the time by its shell-looking syntax and, often, I wasn’t quite sure whether I should add a `\$` sign before a variable name or not, or whether I should use `[...]`, `(...)`, or `{...}`. Now, more than a quarter of century later, I have forgotten most if not all the details about the syntax, and I find it quite difficult to use and somewhat awkward (but perhaps it is my own prejudice). Still, I’m posting this Tcl implementation as a kind of tribute to John Ousterhout, the blessed creator of Tcl-Tk.

``````proc is_disarium {num} {
set n num
set sum 0
set i 1
set ch 1
foreach char [split \$num {}] {
scan \$char %d ch
set sum [ expr (\$sum + \$ch ** \$i)]
incr i
}
return [ expr \$num == \$sum ? 1 : 0]
}
set i 0
set count 0
while { \$count < 19 } {
if [ is_disarium \$i ] {
puts -nonewline  "\${i} "
incr count
}
incr i
}
puts ""
``````

Output:

``````\$ tclsh ./disarium.tcl
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in D

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

bool is_disarium(int num) {
int n = num;
int sum = 0;
ulong len = to!string(num, 10).length;
while (n > 0) {
sum += pow(n % 10, len);
n /= 10;
len--;
}
return num == sum;
}
void main() {
int i = 0;
int count = 0;
while (count < 19) {
if (is_disarium(i)) {
printf("%d ", i);
count++;
}
i++;
}
writeln(" ");
}
``````

Output:

``````0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in Dart

``````import "dart:math";
import "dart:io";
void main() {
var count = 0;
var i = 0;
while (count < 19) {
if (is_disarium(i)) {
stdout.write("\$i ");
count++;
}
i++;
}
}

bool is_disarium(numb) {
var n = numb;
var len = n.toString().length;
var sum = 0;
while (n > 0) {
sum += (pow(n % 10, len)).toInt();
n = (n / 10).toInt();
len--;
}
return numb == sum;
}
``````

Output:

``````0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
``````

### Disarium Numbers in JavaScript

``````function is_disarium (num) {
let n = num
let len = n.toString().length
let sum = 0
while (n > 0) {
sum += (n % 10) ** len
n = parseInt(n / 10, 10)
len--
}
return num == sum
}
let count = 0
let i = 1
while (count < 18) {
if (is_disarium(i)) {
process.stdout.write(i + " ")
count++
}
i++
}
``````

Output:

1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798

You are given a list of integers with no duplicates, e.g. `[0, 1, 2]`.

Write two functions, `permutation2rank()` which will take the list and determine its rank (starting at 0) in the set of possible permutations arranged in lexicographic order, and `rank2permutation()` which will take the list and a rank number and produce just that permutation.

Given the list `[0, 1, 2]` the ordered permutations are:

``````0: [0, 1, 2]
1: [0, 2, 1]
2: [1, 0, 2]
3: [1, 2, 0]
4: [2, 0, 1]
5: [2, 1, 0]
``````

and therefore:

``````permutation2rank([1, 0, 2]) = 2

rank2permutation([0, 1, 2], 1) = [0, 2, 1]
``````

Given that dealing with integers, I do not understand why permutations should be arranged in lexicographic order. I would expect permutation `[9, 11]` to be before permutation `[11, 9]`, but lexicographic order would arrange them the other way around: `[11, 9], [9, 11]`. Well, it doesn’t really matter and we will use in our tests only single digit integers to avoid bizarre results. I’ll even use a test with single letters to show that my implementation also works with letters.

The second thing is that since my implementation of `permutation2rank` creates an ordered array of permutations, we don’t really need the `rank2permutation` subroutine to find the permutation with rank `n`, since I only need to lookup the array. I’ll create the `rank2permutation` subroutine nonetheless, just to abide with the specification.

### Permutation Ranking in Raku

In Raku, the `permutations` method will create permutations in the proper order provided the input permutation is itself in the right order. So we only need to sort the input permutation at the beginning.

``````my @permut_str;

sub permutation2rank(@in) {
# if the input list is sorted, then permutations will be sorted
# Forcing a lexicographic order (although not really needed here)
my @sorted = sort { \$^a leg \$^b }, @in;
my @permutations = @sorted.permutations;
@permut_str = map {[join " ", \$_]}, @permutations;
my %ranks = map { \$^b => \$^a }, @permut_str.kv;
}
sub rank2permutations (\$rank) {
return @permut_str[\$rank];
}

my @tests = (1, 0, 2), (6, 3, 4), <a c d b>;
for @tests -> @test {
my %ranks = permutation2rank(@test);
say @permut_str;
my \$test = join " ", @test;
say "[\$test] has rank %ranks{\$test}";
say "Rank %ranks{\$test} is ", rank2permutations(%ranks{\$test});
say "Rank {%ranks{\$test} - 1} is ", rank2permutations(%ranks{\$test} - 1);
say "";
}
``````

Note that we are also printing the sorted permutations to enable easy verification of the results.

This program displays the following output:

``````\$ raku ./permute_ranks.raku
[[0 1 2] [0 2 1] [1 0 2] [1 2 0] [2 0 1] [2 1 0]]
[1 0 2] has rank 2
Rank 2 is [1 0 2]
Rank 1 is [0 2 1]

[[3 4 6] [3 6 4] [4 3 6] [4 6 3] [6 3 4] [6 4 3]]
[6 3 4] has rank 4
Rank 4 is [6 3 4]
Rank 3 is [4 6 3]

[[a b c d] [a b d c] [a c b d] [a c d b] [a d b c] [a d c b] [b a c d] [b a d c] [b c a d] [b c d a] [b d a c] [b d c a] [c a b d] [c a d b] [c b a d] [c b d a] [c d a b] [c d b a] [d a b c] [d a c b] [d b a c] [d b c a] [d c a b] [d c b a]]
[a c d b] has rank 3
Rank 3 is [a c d b]
Rank 2 is [a c b d]
``````

### Permutation Ranking in Perl

Perl has no built-in function to create permutations, so we implement the recursive `permute` subroutine to do that. Note that we designed it in such a way as to create the permutations in the right order, provided the input permutation is itself in the proper order.

``````use strict;
use warnings;
use feature "say";
use Data::Dumper;

my @permutations;

sub permute {
my (\$done, \$left) = @_;
if (scalar @\$left == 0) {
push @permutations, \$done;
return;
}
my @left = @\$left;
permute([ @\$done, \$left[\$_]], [@left[0..\$_-1], @left[\$_+1..\$#left]]) for 0..\$#left;
}

sub permutation2rank {
# if the input list is sorted, then permutations will be sorted
# This will be in lexicographic order, even for numbers
my @sorted = sort @_;
permute([], [@sorted]);
my @permut_str = map {join " ", @\$_} @permutations;
my \$count = 0;
my %ranks = map { \$_ => \$count++ } @permut_str;
}

sub rank2permutations {
return (map {join " ", @\$_} @permutations)[\$_[0]];
}

my @tests = ( [1, 0, 2], [6, 3, 4], [<a d c b>]);
for my \$test (@tests) {
@permutations = ();
my %ranks = permutation2rank (@\$test);
my \$test_str = join " ", @\$test;
say "Rank of [\$test_str] is: \$ranks{\$test_str}";
for my \$i (2, 4, 5) {
say "Rank \$i is [", rank2permutations (\$i), "]";
}
say " ";
}
``````

This program displays the following output:

``````\$ perl ./permute_ranks.pl
Rank of [1 0 2] is: 2
Rank 2 is [1 0 2]
Rank 4 is [2 0 1]
Rank 5 is [2 1 0]

Rank of [6 3 4] is: 4
Rank 2 is [4 3 6]
Rank 4 is [6 3 4]
Rank 5 is [6 4 3]

Rank of [a d c b] is: 5
Rank 2 is [a c b d]
Rank 4 is [a d b c]
Rank 5 is [a d c b]
``````

### Permutation Ranking in Julia

Note that Julia array subscripts start at 1, not 0. Therefore, the ranks are shifted by 1 compared to other languages and the output differs accordingly. It would be easy to fix that, but I preferred to keep the Julia semantic.

``````# Note: Julia array subscripts start at 1, not 0
using Combinatorics

function permute(in_list)
return collect(permutations(sort(in_list), length(in_list)))
end

function permutation2rank(perms, input)
for i in 1:length(perms)
if perms[i] == input
return i
end
end
end

function rank2permutation(perm_list, index)
return perm_list[index]
end

perm_in = [3, 1, 2]
perms = permute(perm_in)
println("Permutations: ", perms)
println("Permutation ", perm_in, " -> rank ", permutation2rank(perms, perm_in))
for i in 1:length(perms)
println("Rank: ", i, " -> permutation ", rank2permutation(perms, i))
end
``````

Output:

``````\$ julia ./permute_ranks.jl
Permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Permutation [3, 1, 2] -> rank 5
Rank: 1 -> permutation [1, 2, 3]
Rank: 2 -> permutation [1, 3, 2]
Rank: 3 -> permutation [2, 1, 3]
Rank: 4 -> permutation [2, 3, 1]
Rank: 5 -> permutation [3, 1, 2]
Rank: 6 -> permutation [3, 2, 1]
``````

### Permutation Ranking in Python

Comparing two arrays with the `==` operator doesn’t seem to work in Python. There may be a better way to compare arrays, but I decided to stringify the arrays and to compare the resulting strings.

``````def stringify(input):
return " ".join(map(str, input))

def permute(input):
temp = input.copy() # avoid modifying input perm with the sort
temp.sort()
return list(itertools.permutations(temp))

def permutation2rank(perms, input):
perms_str = map(stringify, perms)
input_str = stringify(input)
for index, value in enumerate(perms_str):
if value == input_str:
return index

def rank2permutation(permutation, rank):
return permutation[rank]

perm = [3, 1, 2]
perms = permute(perm)
print("Permutations: ", str(perms))
rank = permutation2rank(perms, perm)
print("Permutation ", perm, " -> rank ", rank)
for i in range(0, len(perms)):
print("Rank: ", i, " -> permutation ", rank2permutation(perms, i))
``````

Output:

``````\$ python3 ./permute_ranks.py
Permutations:  [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
Permutation  [3, 1, 2]  -> rank  4
Rank:  0  -> permutation  (1, 2, 3)
Rank:  1  -> permutation  (1, 3, 2)
Rank:  2  -> permutation  (2, 1, 3)
Rank:  3  -> permutation  (2, 3, 1)
Rank:  4  -> permutation  (3, 1, 2)
Rank:  5  -> permutation  (3, 2, 1)
``````

### Permutation Ranking in Ruby

``````def permute(in_list)
return in_list.sort.permutation(in_list.length).to_a
end

def permutation2rank(perms, input)
for i in 0..perms.length - 1
if perms[i] == input
return i
end
end
end

def rank2permutation(perms, index)
return perms[index]
end

perm_in = [3, 1, 2]
perms = permute(perm_in)
puts("Permutations: #{perms} \n")
print("Permutation #{perm_in} -> rank  #{permutation2rank(perms, perm_in)} \n")
for i in 1..perms.length - 1
print("Rank:  #{i} -> permutation  #{rank2permutation(perms, i)} \n")
end
``````

Output:

``````Permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Permutation [3, 1, 2] -> rank 4
Rank: 1 -> permutation [1, 3, 2]
Rank: 2 -> permutation [2, 1, 3]
Rank: 3 -> permutation [2, 3, 1]
Rank: 4 -> permutation [3, 1, 2]
Rank: 5 -> permutation [3, 2, 1]
``````

### Permutation Ranking in Javascript

JavaScript doesn’t seem to have a built-in permutation function. The `permute` function in the program below is derived from this Stack Overflow page. I liked it because of its functional style. When I used JavaScript around 2003-04 for Web page development, I did not like too much its somewhat clunky syntax. Taking a fresh look at it nowadays really changes my perception, it appears that the language has really improved in the meantime. I’ll try to look deeper into it as soon as I get some free time.

``````function permute(inputArray) {
let inAry = [...inputArray].sort(); //copy and sort input
return inAry.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key)
.concat(arr.slice(key + 1))
.reduce(permute, [])
.map(function (perm) {
return [item].concat(perm);
}) || item);
}, []);
}

function permutation2rank(perms, in_perm) {
let input = JSON.stringify(in_perm)
for (var i = 0; i < perms.length; i++) {
// stringify permutations to enable comparison
if (JSON.stringify(perms[i]) == input) {
return i
}
}
}

function rank2permutation(perm_list, index) {
return perm_list[index]
}

let perm_in = [3, 1, 2];
let perms = permute(perm_in)
console.log(perms)
let rank = permutation2rank(perms, perm_in)
console.log("Permutation", perm_in, "has rank", rank)
for (var i = 0; i < perms.length; i++) {
console.log("Rank: ", i, " -> permutation ", rank2permutation(perms, i))
}
``````

Output:

``````node /tmp/CUuyiMw4x0.js
[ [ 1, 2, 3 ],
[ 1, 3, 2 ],
[ 2, 1, 3 ],
[ 2, 3, 1 ],
[ 3, 1, 2 ],
[ 3, 2, 1 ] ]
Permutation [ 3, 1, 2 ] has rank 4
Rank:  0  -> permutation  [ 1, 2, 3 ]
Rank:  1  -> permutation  [ 1, 3, 2 ]
Rank:  2  -> permutation  [ 2, 1, 3 ]
Rank:  3  -> permutation  [ 2, 3, 1 ]
Rank:  4  -> permutation  [ 3, 1, 2 ]
Rank:  5  -> permutation  [ 3, 2, 1 ]
``````

## 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 July 31, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.