Perfect totient numbers

From Rosetta Code
Task
Perfect totient numbers
You are encouraged to solve this task according to the task description, using any language you may know.

Generate and show here, the first twenty Perfect totient numbers.


Related task


Also see



C[edit]

Calculates as many number of perfect Totient numbers as entered on the command line.

#include<stdlib.h>
#include<stdio.h>
 
long totient(long n){
long tot = n,i;
 
for(i=2;i*i<=n;i+=2){
if(n%i==0){
while(n%i==0)
n/=i;
tot-=tot/i;
}
 
if(i==2)
i=1;
}
 
if(n>1)
tot-=tot/n;
 
return tot;
}
 
long* perfectTotients(long n){
long *ptList = (long*)malloc(n*sizeof(long)), m,count=0,sum,tot;
 
for(m=1;count<n;m++){
tot = m;
sum = 0;
while(tot != 1){
tot = totient(tot);
sum += tot;
}
if(sum == m)
ptList[count++] = m;
}
 
return ptList;
}
 
long main(long argC, char* argV[])
{
long *ptList,i,n;
 
if(argC!=2)
printf("Usage : %s <number of perfect Totient numbers required>",argV[0]);
else{
n = atoi(argV[1]);
 
ptList = perfectTotients(n);
 
printf("The first %d perfect Totient numbers are : \n[",n);
 
for(i=0;i<n;i++)
printf(" %d,",ptList[i]);
printf("\b]");
}
 
return 0;
}
 

Output for multiple runs, a is the default executable file name produced by GCC

C:\rossetaCode>a 10
The first 10 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255]
C:\rossetaCode>a 20
The first 20 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571]
C:\rossetaCode>a 30
The first 30 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571, 6561, 8751, 15723, 19683, 36759, 46791, 59049, 65535, 140103, 177147]
C:\rossetaCode>a 40
The first 40 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571, 6561, 8751, 15723, 19683, 36759, 46791, 59049, 65535, 140103, 177147, 208191, 441027, 531441, 1594323, 4190263, 4782969, 9056583, 14348907, 43046721, 57395631]

Factor[edit]

USING: formatting kernel lists lists.lazy math
math.primes.factors ;
 
: perfect? ( n -- ? )
[ 0 ] dip dup [ dup 2 < ] [ totient tuck [ + ] 2dip ] until
drop = ;
 
20 1 lfrom [ perfect? ] lfilter ltake list>array
"%[%d, %]\n" printf
Output:
{ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571 }

Go[edit]

package main
 
import "fmt"
 
func gcd(n, k int) int {
if n < k || k < 1 {
panic("Need n >= k and k >= 1")
}
 
s := 1
for n&1 == 0 && k&1 == 0 {
n >>= 1
k >>= 1
s <<= 1
}
 
t := n
if n&1 != 0 {
t = -k
}
for t != 0 {
for t&1 == 0 {
t >>= 1
}
if t > 0 {
n = t
} else {
k = -t
}
t = n - k
}
return n * s
}
 
func totient(n int) int {
tot := 0
for k := 1; k <= n; k++ {
if gcd(n, k) == 1 {
tot++
}
}
return tot
}
 
func main() {
var perfect []int
for n := 1; len(perfect) < 20; n += 2 {
tot := n
sum := 0
for tot != 1 {
tot = totient(tot)
sum += tot
}
if sum == n {
perfect = append(perfect, n)
}
}
fmt.Println("The first 20 perfect totient numbers are:")
fmt.Println(perfect)
}
Output:
The first 20 perfect totient numbers are:
[3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571]

The following much quicker version uses Euler's product formula rather than repeated invocation of the gcd function to calculate the totient:

package main
 
import "fmt"
 
func totient(n int) int {
tot := n
for i := 2; i*i <= n; i += 2 {
if n%i == 0 {
for n%i == 0 {
n /= i
}
tot -= tot / i
}
if i == 2 {
i = 1
}
}
if n > 1 {
tot -= tot / n
}
return tot
}
 
func main() {
var perfect []int
for n := 1; len(perfect) < 20; n += 2 {
tot := n
sum := 0
for tot != 1 {
tot = totient(tot)
sum += tot
}
if sum == n {
perfect = append(perfect, n)
}
}
fmt.Println("The first 20 perfect totient numbers are:")
fmt.Println(perfect)
}

The output is the same as before.

Haskell[edit]

import Data.Bool (bool)
 
perfectTotients :: [Int]
perfectTotients =
[2 ..] >>=
((bool [] . return) <*>
((==) <*> (succ . sum . tail . takeWhile (1 /=) . iterate φ)))
 
φ :: Int -> Int
φ = memoize (\n -> length (filter ((1 ==) . gcd n) [1 .. n]))
 
memoize :: (Int -> a) -> (Int -> a)
memoize f = (map f [0 ..] !!)
 
main :: IO ()
main = print $ take 20 perfectTotients
Output:
[3,9,15,27,39,81,111,183,243,255,327,363,471,729,2187,2199,3063,4359,4375,5571]

JavaScript[edit]

(() => {
'use strict';
 
// main :: IO ()
const main = () =>
showLog(
take(20, perfectTotients())
);
 
// perfectTotients :: Generator [Int]
function* perfectTotients() {
const
phi = memoized(
n => length(
filter(
k => 1 === gcd(n, k),
enumFromTo(1, n)
)
)
),
imperfect = n => n !== sum(
tail(iterateUntil(
x => 1 === x,
phi,
n
))
);
let ys = dropWhileGen(imperfect, enumFrom(1))
while (true) {
yield ys.next().value - 1;
ys = dropWhileGen(imperfect, ys)
}
}
 
// GENERIC FUNCTIONS ----------------------------
 
// abs :: Num -> Num
const abs = Math.abs;
 
// dropWhileGen :: (a -> Bool) -> Gen [a] -> [a]
const dropWhileGen = (p, xs) => {
let
nxt = xs.next(),
v = nxt.value;
while (!nxt.done && p(v)) {
nxt = xs.next();
v = nxt.value;
}
return xs;
};
 
// enumFrom :: Int -> [Int]
function* enumFrom(x) {
let v = x;
while (true) {
yield v;
v = 1 + v;
}
}
 
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
m <= n ? iterateUntil(
x => n <= x,
x => 1 + x,
m
) : [];
 
// filter :: (a -> Bool) -> [a] -> [a]
const filter = (f, xs) => xs.filter(f);
 
// gcd :: Int -> Int -> Int
const gcd = (x, y) => {
const
_gcd = (a, b) => (0 === b ? a : _gcd(b, a % b)),
abs = Math.abs;
return _gcd(abs(x), abs(y));
};
 
// iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
const iterateUntil = (p, f, x) => {
const vs = [x];
let h = x;
while (!p(h))(h = f(h), vs.push(h));
return vs;
};
 
// Returns Infinity over objects without finite length.
// This enables zip and zipWith to choose the shorter
// argument when one is non-finite, like cycle, repeat etc
 
// length :: [a] -> Int
const length = xs =>
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
 
// memoized :: (a -> b) -> (a -> b)
const memoized = f => {
const dctMemo = {};
return x => {
const v = dctMemo[x];
return undefined !== v ? v : (dctMemo[x] = f(x));
};
};
 
// showLog :: a -> IO ()
const showLog = (...args) =>
console.log(
args
.map(JSON.stringify)
.join(' -> ')
);
 
// sum :: [Num] -> Num
const sum = xs => xs.reduce((a, x) => a + x, 0);
 
// tail :: [a] -> [a]
const tail = xs => 0 < xs.length ? xs.slice(1) : [];
 
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = (n, xs) =>
'GeneratorFunction' !== xs.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
 
// MAIN ---
main();
})();
Output:
[3,9,15,27,39,81,111,183,243,255,327,363,471,729,2187,2199,3063,4359,4375,5571]


Perl[edit]

Library: ntheory
use ntheory qw(euler_phi);
 
sub phi_iter {
my($p) = @_;
euler_phi($p) + ($p == 2 ? 0 : phi_iter(euler_phi($p)));
}
 
my @perfect;
for (my $p = 2; @perfect < 20 ; ++$p) {
push @perfect, $p if $p == phi_iter($p);
}
 
printf "The first twenty perfect totient numbers:\n%s\n", join ' ', @perfect;
Output:
The first twenty Perfect totient numbers:
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571

Perl 6[edit]

Works with: Rakudo version 2018.11
my \𝜑  = Nil, |(1..*).hyper.map: -> $t { +(^$t).grep: * gcd $t == 1 };
my \𝜑𝜑 = Nil, |(2..*).grep: -> $p { $p == sum 𝜑[$p], { 𝜑[$_] }1 };
 
put "The first twenty Perfect totient numbers:\n", 𝜑𝜑[1..20];
Output:
The first twenty Perfect totient numbers:
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571

Python[edit]

from math import gcd
from functools import lru_cache
from itertools import islice, count
 
@lru_cache(maxsize=None)
def φ(n):
return sum(1 for k in range(1, n + 1) if gcd(n, k) == 1)
 
def perfect_totient():
for n0 in count(1):
parts, n = 0, n0
while n != 1:
n = φ(n)
parts += n
if parts == n0:
yield n0
 
 
if __name__ == '__main__':
print(list(islice(perfect_totient(), 20)))
Output:
[3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571]

REXX[edit]

/*REXX program  calculates and displays  the first   N   perfect totient  numbers.      */
parse arg N . /*obtain optional argument from the CL.*/
if N=='' | N=="," then N= 20 /*Not specified? Then use the default.*/
p= 0 /*the count of perfect totient numbers.*/
@.=. /*memoization array of totient numbers.*/
$= /*list of the perfect totient numbers. */
do j=3 by 2 until p==N; s= phi(j) /*obtain totient number for a number. */
a= s /* [↓] search for a perfect totient #.*/
do until a==1; a= phi(a); s= s + a
end /*until*/
if s\==j then iterate /*Is J not a perfect totient number? */
p= p + 1 /*bump count of perfect totient numbers*/
$= $ j /*add to perfect totient numbers list. */
end /*j*/
 
say 'The first ' N " perfect totient numbers:" /*display the header to the terminal. */
say strip($) /* " " list. " " " */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
gcd: parse arg x,y; do until y==0; parse value x//y y with y x; end /*until*/
return x
/*──────────────────────────────────────────────────────────────────────────────────────*/
phi: procedure expose @.; parse arg z; if @.z\==. then return @.z /*was found before?*/
#= z==1; do m=1 for z-1; if gcd(m, z)==1 then #= # + 1; end /*m*/
@.z= #; return # /*use memoization. */
output   when using the default input of :     20
The first  20  perfect totient numbers:
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571

Sidef[edit]

func perfect_totient({.<=1}, sum=0) { sum }
func perfect_totient( n, sum=0) { __FUNC__(var(t = n.euler_phi), sum + t) }
 
say (1..Inf -> lazy.grep {|n| perfect_totient(n) == n }.first(20))
Output:
[3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571]

zkl[edit]

var totients=List.createLong(10_000,0);	// cache
fcn totient(n){ if(phi:=totients[n]) return(phi);
totients[n]=[1..n].reduce('wrap(p,k){ p + (n.gcd(k)==1) })
}
fcn perfectTotientW{ // -->iterator
(1).walker(*).tweak(fcn(z){
parts,n := 0,z;
while(n!=1){ parts+=( n=totient(n) ) }
if(parts==z) z else Void.Skip;
})
}
perfectTotientW().walk(20).println();
Output:
L(3,9,15,27,39,81,111,183,243,255,327,363,471,729,2187,2199,3063,4359,4375,5571)