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.

Task 1: Damm Algorithm

You are given a positive number, $n.

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

Please checkout the wikipedia page for information.

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.

Task 1: Permuted Multiples

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();
    return to!int(d.joiner);
}

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

Task 2: Reversible Numbers

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.

Task 1: Last Sunday

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

Write a script to generate first 20 Perfect Totient Numbers. Please checkout [wikipedia page](https://en.wikipedia.org/wiki/Perfect_totient_number] for more informations.

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 Rustnum::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
li      # loads iteration variable
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
li      # loads iteration variable
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.

Task 1: Disarium Numbers

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
li      # loads iteration variable
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

Task 2: Permutation Ranking

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.

Please checkout this post for more informations and algorithm.

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.