Sundays and totients

Weekly challenge 175 — 25 July 2022

Week 175: 25 Jul 2022

Task 2

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

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); }

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)

Any content of this website which has been created by Peter Campbell Smith is in the public domain