Task — Perfect totient numbers

Write a script to generate first 20 Perfect Totient Numbers. Please see this Wikipedia page for more information.

Analysis

Wikipedia tells us that 'In number theory, a perfect totient number is an integer that is equal to the sum of its iterated totients. That is, one applies the totient function to a number n, apply it again to the resulting totient, and so on, until the number 1 is reached, and adds together the resulting sequence of numbers; if the sum equals n, then n is a perfect totient number'.

This task requires to us write a script to generate the first 20 perfect totient numbers. To do this for a given number n, we first count its mutually prime lesser integers (including 1) - or equivalently, those lesser numbers with which it has a greatest common divisor of 1.

Having got this count, we repeat the process on that number - that is, count its lesser mutual primes, and so until we get to 1. Clearly it will always converge to 1, because the count of positive integers less than n will always be less than n.

So how to do this? First I acquired a gcd function, and then wrote a totients_count function. That was enough for the first few perfect totients, but as they get bigger it takes longer, so I had totients_count cache its results in an array, and checked for an answer there before calling totients_count again.

On my (quite slow) machine it takes about 1.5 minutes to get the required 20 numbers.

#!/usr/bin/perl

# Peter Campbell Smith - 2022-07-25
# PWC 175 task 2

use v5.28;
use utf8;
use warnings;
binmode(STDOUT, ':utf8');

my ($trial, $sum, $number, $tc, $target, $found, $string, @tc);

# loop up from 2
$target = 20;
$found = 0;
my $start = time;

TRIAL: for $trial (2 .. 10000) {
    $sum = 0;   
    $number = $trial;
    
    # loop over totients
    while (1) {
        $tc = defined $tc[$number] ? $tc[$number] :  # if we've calculated it already
            totient_count($number);                  # or calculate it if not
        $sum += $tc;
        next TRIAL if $sum > $trial;   # give up as we've already exceeded $trial
        last if $tc == 1;              # summation has converged to 1
        $number = $tc;                 # and if it hasn't, get the tc of the tc
    }
    
    # save if we have a reault
    next TRIAL unless $sum == $trial;
    $string .= qq[$sum, ];
    last if ++ $found == $target;
}
say qq[\nInput:  $target perfect totient numbers];
printf (qq[Output: %s (took %d secs)], substr($string, 0, -2), time - $start);

sub totient_count {
    
    # counts the mutually primes less than the argument
    my ($number, $j, $count);
    $number = $_[0];
    
    $count = 0;
    for $j (1 .. $number - 1) {
        $count++ if gcd($j, $number) == 1;   # a and b are mutually prime if their gcd is 1
    }
    $tc[$number] = $count;   # cache this for future use
    return $count;
}
                
sub gcd {
    
    # calculates greatest common divisor of $a and $b
    my ($a, $b) = @_;
    return 0 == $b ? $a : gcd($b, $a % $b);
}
        

Output

Input:  20 perfect totient numbers
Output: 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 
363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571 
(took 97 secs)