## 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 class*method*day-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 is*perfect*totient(i):
print(i, end = ” “)
count += 1
i += 1
print(” “)

Output:

```
$ time python3 ./perfect-totient.py
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
real 0m4,832s
user 0m4,718s
sys 0m0,076s
```

### Perfect Totient Numbers in Kotlin

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

function.

```
val cache = Array(10000, {i-> 0})
fun gcd (m: Int, n: Int): Int {
var i = m
var j = n
while(j != 0) {
val k = j
j = i % j
i = k
}
return i
}
fun is_perfect_totient(n: Int): Boolean {
var tot = 0
for (i in 1..n-1) {
if (gcd(n, i) == 1) {
tot++
}
}
val sum = tot + cache[tot]
cache[n] = sum
return n == sum
}
fun main() {
var i = 0
var count = 0
while (count <= 20) {
if (is_perfect_totient(i)) {
print("$i ")
count++
}
i++
}
println(" ")
}
```

Output:

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

This program ran in 2.5 seconds.

### Perfect Totient Numbers in Rust

The Rust`num::integer`

library provides a `gcd`

function. In my humble opinion, Rust is nevertheless a pain in the neck to use because of its ultra-strict type system. As an example, I could not use a simple integer (`i32`

) as an array subscript, because Rust wants a `usize`

type. That’s why I had to use expressions like `CACHE[n as usize]`

. Similarly, Rust forced me to have my global cache array in uppercase. And, since it is a global variable, I had to wrap accesses to the cache in a `unsafe{]`

block. I personally don’t think a programming language should get in the way of developers to such an extent. I really wasted quite a bit of time working around this straitjacket.

```
use num::integer::gcd;
static mut CACHE:[i32;10000] = [0; 10000];
fn is_perfect_totient(n: i32) -> bool {
let mut tot = 0;
for i in 1..n {
if gcd(n, i) == 1 {
tot += 1
}
}
unsafe {
let sum = tot + CACHE[tot as usize];
CACHE[n as usize] = sum;
return n == sum;
}
}
fn main() {
let mut i = 1;
let mut count = 0;
while count < 20 {
if is_perfect_totient(i) {
print!("{} ", i);
count += 1;
}
i += 1;
}
println!("{}", " ")
}
```

Ouput:

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

### Perfect Totient Numbers in Java

Java has a `gcd`

function bizarrely sitting in the `java.math.BigInteger`

class. For a program performing heavy number crunching, I did not think it was reasonable to accept the performance penalty associated with big integers. So, I wrote my own `gcd`

function.

```
public class PerfectTotient {
static int[] cache = new int[10000];
public static int gcd(int i, int j) {
while (j != 0) {
int temp = i % j;
i = j;
j = temp;
}
return i;
}
public static boolean isPerfectTotient(int n) {
int tot = 0;
for (int i = 1; i < n; i++) {
if (gcd(n, i) == 1) {
tot++;
}
}
int sum = tot + cache[tot];
cache[n] = sum;
return n == sum;
}
public static void main(String[] args) {
int i = 0;
int count = 0;
while (count < 20) {
if (isPerfectTotient(i)) {
System.out.printf("%d ", i);
count++;
}
i++;
}
System.out.printf("%s", "\n");
}
}
```

Ouput:

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

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

### Perfect Totient Numbers in Nim

Nim has a `gcd`

function in its `math`

library.

```
import math
var cache: array[0..10000, int]
proc is_perfect_totient (n: int): bool =
var tot = 0
for i in 1..n-1:
if (gcd(n, i) == 1):
tot += 1
let sum = tot + cache[tot]
cache[n] = sum
return sum == n
var i = 1
var count = 0
while count < 20:
if is_perfect_totient(i):
stdout.write i, " "
count += 1
i += 1
echo ""
```

Output:

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

This program ran in 13 seconds.

### Perfect Totient Numbers in Go

No `gcd`

in plementation in go, so we rolled out our own.

```
import "fmt"
var cache [10000]int
func gcd(i int, j int) int {
for j != 0 {
temp := i % j
i = j
j = temp
}
return i
}
func is_perfect_totient(n int) bool {
tot := 0
for i := 1; i < n; i++ {
if gcd(n, i) == 1 {
tot++
}
}
sum := tot + cache[tot]
cache[n] = sum
return n == sum
}
func main() {
i := 0
count := 0
for count <= 20 {
if is_perfect_totient(i) {
fmt.Printf("%d ", i)
count++
}
i++
}
fmt.Println("")
}
```

Output:

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

### Perfect Totient Numbers in JavaScript

```
var cache = new Array(10000)
cache[0] = 0
function gcd (i, j) {
while(j != 0) {
k = j
j = i % j
i = k
}
return i
}
function is_perfect_totient (n) {
let tot = 0
for (var i = 1; i < n; i++) {
if (gcd(n, i) == 1) {
tot++
}
}
sum = tot + cache[tot]
cache[n] = sum
return n == sum
}
let count = 0
let i = 1
while (count < 20) {
if (is_perfect_totient(i)) {
process.stdout.write(i + " ")
count++
}
i++
}
process.stdout.write("\n")
```

Output:

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

### Perfect Totient Numbers in Dart

Dart has a `gcd`

method, which we will use.

```
import "dart:io";
var cache = List<int>.filled(10000, 0, growable: true);
void main() {
cache[0] = 0;
var count = 0;
var i = 1;
while (count < 20) {
if (is_perfect_totient(i)) {
stdout.write("$i ");
count++;
}
i++;
}
print(" ");
}
bool is_perfect_totient(n) {
var tot = 0;
for (int i = 1; i < n; i++ ) {
if (i.gcd(n) == 1) {
tot++;
}
}
int sum = tot + cache[tot];
cache[n] = sum;
return n == sum;
}
```

Output:

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

### Perfect Totient Numbers in Ruby

Ruby has a `gcd`

mehod, so we’ll use it.

```
$cache = Array.new(10000, 0) # global variables require $
def is_perfect_totient(n)
tot = 0
for i in 1..(n - 1)
if n.gcd(i) == 1
tot += 1
end
end
sum = tot + $cache[tot]
$cache[n] = sum;
return sum == n
end
i = 1
count = 0
while count < 20
if is_perfect_totient(i)
printf("%d ", i)
count += 1
end
i += 1
end
print("\n")
```

Output:

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

### Perfect Totient Numbers in Scala

Scala has a `gcd`

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

function for plain integers.

```
object PerfectTotient extends App {
var cache = new Array[Int](10000)
def gcd(a: Int, b: Int): Int = {
var (i, j) = (a, b)
while (j > 0) {
var t = i
i = j
j = t % j
}
return i
}
def is_perfect_totient(n: Int): Boolean = {
var tot = 0
for (i <- 1 to (n - 1)) {
if (gcd(n, i) == 1) {
tot += 1
}
}
val sum = tot + cache(tot)
cache(n) = sum
return n == sum
}
var i = 1
var count = 0
while (count < 20) {
if (is_perfect_totient(i)) {
count += 1
printf("%d ", i)
}
i += 1
}
println("")
}
```

Output:

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

### Perfect Totient Numbers in Tcl

Tcl doesn’t have a built-in `gcd`

function, so I wrote one.

```
array set cache {}
set cache(0) 0
proc gcd {i j} {
while {$j != 0} {
set t [expr {$i % $j}]
set i $j
set j $t
}
return $i
}
proc is_perfect_totient {n} {
global cache
set tot 0
for {set i 1} {$i < $n} {incr i} {
if [ expr [gcd $i $n] == 1 ] {
incr tot
}
}
set sum [expr $tot + $cache($tot)]
set cache($n) $sum
return [ expr $n == $sum ? 1 : 0]
}
set i 1
set count 0
while { $count < 20 } {
if [ is_perfect_totient $i ] {
puts -nonewline "${i} "
incr count
}
incr i
}
puts ""
```

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

```
$ time tclsh ./perfect-totient.tcl
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
real 1m18,058s
user 1m17,593s
sys 0m0,046s
```

## Wrapping up

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

## Leave a comment