# 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.
I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.
Leave a comment