laurent_r

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.