Perfect totient numbers

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

Related task

Totient function

Also see

the OEIS entry for perfect totient numbers.

Go

<lang go>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)

}</lang>

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: <lang go>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)

}</lang>

The output is the same as before.

Perl 6

Works with: Rakudo version 2018.11

<lang perl6>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];</lang>

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

<lang python>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)))</lang>

Output:

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

<lang rexx>/*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. */</lang>

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

<lang ruby>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))</lang>

Output:

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

zkl

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

}</lang> <lang zkl>perfectTotientW().walk(20).println();</lang>

Output:

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