Month: July 2022

Wherein we assess our personal spaces. Over and over. Until we get it just right.

THE WEEKLY CHALLENGE – PERL & RAKU #175 Task 2

---

“There is a perfection in everything that cannot be owned.” 

— Anaïs Nin, Delta of Venus

---

Perfect Totient Numbers

Submitted by: Mohammad S Anwar

Write a script to generate first 20 Perfect Totient Numbers. Please checkout wikipedia page for more informations.

Output

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

ANALYSIS

First things first: so, um, what is a totient number? Well, it is the result of Euler’s Totient Function, of course. And what that is, in the most literally descriptive sense, is the count of positive integer values less than the number that are also coprime with it — which is to say the two numbers do not share a common prime factor.

Ok. Thats… an unusual request.

The obvious followup question, why would we do this, is considerably harder to answer. The function, it turns out, appears in several analyses of prime factorization — which makes a certain intuitive sense, being itself a function of this — as well as in analysis of the greatest common divisor function. In the latter connection we can see a similar parallel relationship to the underlying process of searching through divisors instead of factors.

So the process of the function can be connected to similar processes in other functions, tying it in to the world of mathematical analysis. This makes a certain primitive, tautological sense. We can then take this as a foothold as to why such an abstract idea would receive as much study as it has. Oddly, those connections have been shown to run deep. That Leonhard Euler fellow was apparently on to something.

One of the most interesting appearances of the function is in an equality binding Binet’s closed form equation for the Fibonacci sequence, the Möbius function and Euler’s totient function.

It’s not quite as elegant as

another one of Euler’s, by the way, but it’s getting there. Both of these wrap around the value of e, Euler’s constant, which also makes sense, given what Euler was up to.

The most visible use of the totient function identities is in the basis of the RSA encryption scheme, where an application of the function is used to construct the “public” — freely distributed — encryption key for the process. This allows anyone to encrypt a message to the possessor of the “private” decryption key.

But wait! We’re only halfway there. Or really, practically speaking, we’ve only now just gotten into the car. To actually arrive at the destination for this specific application, we calculate the totient as an iterated function, reapplying the function to the previously calculated totient until a value if 1 is reached.

As the totient must be less than or equal to the number it’s derived from — we’re making a count of numbers from the range 1 to the number — the iteration in practice inexorably drives the result downward until 1 is reached. The totient of 1 is 1, so past that point the iteration is robustly defined and can no longer change the result.

The next abstraction is that once we have achieved a totient of 1, we sum the sequence of totients that got us there, including the final 1. If this value equals the original number, we have a perfect totient number. This is analogous to a perfect number, where the divisors are summed and compared to the source. It is not, however, the exact complement function — which would be the sum of the non-divisors — but rather only those numbers who have a GCD of 1 with the source, in that they share no prime factors.

The sum of the non-divisors wouldn’t be very interesting as far as perfection goes, as I believe every number above 4 will be abundant, or exceed the value. Perhaps someone has studied abundant totient numbers, probably or even surely if you think about number theorists, up in some garret with an oak desk, a pencil and a ream of paper, the tools of the trade. I think it safe to say anything you can dream up, somewhere someone has looked at it at least once.

The perfect totients, as it works out, are interesting, albeit not overly practical. But interesting, nonetheless.

METHOD

To find our totients we need to factor a lot of values; that’s a given. Ultimately we need to look at all numbers less than the given candidate and assess each vis-à-vis the factors of our target. We could create a way to cache the lists of factors for each number, or numbers for each factor, and use these caches to avoid repeatedly factoring the same values over and over. The whole thing sounds doable, but challenging.

Or we can find a totient function and use that. I’m in a bit of a hurry this week so we’ll do it that way.

PERL 5 SOLUTION

To find our totients we’ll move away from factoring and employ the arts of ntheory, another name for the module Math::Prime::Util. This gives us the function euler_phi, which provides an implementation of Euler’s totient function.

We’ll create a subroutine to iterate our totient function, keeping a running sum, until the final totient is 1. After this the sum is returned. That provides the central logical core, and we test numbers going upwards for equality between the iterate_phi function and the value being tested. When 20 equal values have been collected we have achieved our goal.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

## phi is Euler's totient function
use ntheory qw ( euler_phi );

## input
my $limit = shift @ARGV // 20;
my $count = 0;
my $i = 1;
my @out;

while (++$i and $count < 20) {
    $count++ and push @out, $i if $i == iterate_phi($i);
}

## output
say "@out";


sub iterate_phi ( $n, $s = 1 ) {
## given a value we iterate Euler's totient function on it 
## until we arrive at a totient of 1, compounding an aggregate sum of the results 
## this technique skips the final totient, 1, so we add it at the beginning
## - it will always be there.
    $s += $n while ($n = euler_phi($n)) != 1;
    return $s;
}