Perfect totient numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added Perl example)
m (→‎{{header|Perl}}: reformat and simplify the Perl entry)
Line 207: Line 207:
<lang perl>use ntheory qw(euler_phi);
<lang perl>use ntheory qw(euler_phi);


sub phi_iter {
⚫
sub phi_iter { my($p) = @_; return euler_phi($p) + ($p == 2 ? 0 : phi_iter(euler_phi($p))) }
⚫
my($p) = @_;
⚫
euler_phi($p) + ($p == 2 ? 0 : phi_iter(euler_phi($p)));
}


my @perfect;
$p = 1;
for (my $p = 2; @perfect < 20 ; ++$p) {
while () {
⚫
$p++;
push @perfect, $p if $p == phi_iter($p);
push @perfect, $p if $p == phi_iter($p);
last if 20 == @perfect;
}
}

printf "The first twenty perfect totient numbers:\n%s\n", my $result = join ' ', @perfect;</lang>
printf "The first twenty perfect totient numbers:\n%s\n", my $result = join ' ', @perfect;</lang>
{{out}}
{{out}}
<pre>The first twenty Perfect totient numbers:
<pre>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</pre>
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571</pre>

=={{header|Perl 6}}==
=={{header|Perl 6}}==
{{works with|Rakudo|2018.11}}
{{works with|Rakudo|2018.11}}

Revision as of 04:56, 8 December 2018

Perfect totient numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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


Related task


Also see



C

Calculates as many number of perfect Totient numbers as entered on the command line, 40 numbers take around 320 seconds on a Core i5 with 8 GB RAM. <lang C> /*Abhishek Ghosh, 8th December 2018*/

  1. include<stdlib.h>
  2. 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; } </lang> 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]

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

Library: ntheory

<lang perl>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", my $result = join ' ', @perfect;</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

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]

REXX

<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)
Retrieved from "https://rosettacode.org/wiki/Perfect_totient_numbers?oldid=286851"