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)

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain