Perfect totient numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
m (Added a link to the first 54 perfect totient numbers)
m (→‎{{header|REXX}}: changed whitespace in the the GCD function.)
Line 622: Line 622:
exit /*stick a fork in it, we're all done. */
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*/
gcd: parse arg x,y; do until y==0; parse value x//y y with y x; end; return x
return x
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
phi: procedure expose @.; parse arg z; if @.z\==. then return @.z /*was found before?*/
phi: procedure expose @.; parse arg z; if @.z\==. then return @.z /*was found before?*/

Revision as of 21:59, 11 December 2018

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

Calculates as many number of perfect Totient numbers as entered on the command line. <lang C>#include<stdlib.h>

  1. 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]

Factor

<lang factor>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</lang>

Output:
{ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571 }

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.

Haskell

<lang haskell>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</lang>

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

JavaScript

<lang javascript>(() => { 

   '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();

})();</lang>

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

Pascal

I am using a really big array to calculate the Totient of every number up to 1.162.261.467, the 46.te perfect totient number. ( I can only test up to 1.5e9 before I get - out of memory ( 6.5 GB ) ). I'm doing this by using only prime numbers to . With limit 57395631 it takes "real 0m3,661s " The c-program takes "real 3m12,481s" <lang pascal>{$IFdef FPC} 

 {$MODE DELPHI}
 {$CodeAlign proc=32,loop=1}

{$IFEND} //global uses 

 sysutils;

const 

 cLimit = 1162261467;

var 

 TotientList : array of LongWord;
 Sieve : Array of byte;
 T1,T0 : INt64;

procedure SieveInit(svLimit:NativeUint); //prime sieving only odd primes and "compress" them to delta //to reduce memory footprint var 

 pSieve:pByte;
 i,j,pr :NativeUint;

Begin 

 svlimit := (svLimit+1) DIV 2;
 setlength(sieve,svlimit+1);
 pSieve := @Sieve[0];
 For i := 1 to svlimit do
 Begin
   IF pSieve[i]= 0 then
   Begin
     pr := 2*i+1;
     j := (sqr(pr)-1) DIV 2;
     IF  j> svlimit then
       BREAK;
     repeat
       pSieve[j]:= 1;
       inc(j,pr);
     until j> svlimit;
   end;
 end;
 // convert in to delta 
 pr := 0;
 j := 0;
 For i := 1 to svlimit do
 Begin
   IF pSieve[i]= 0 then
   Begin
     pSieve[j] := i-pr;
     inc(j);
     pr := i;
   end;
 end;
 setlength(sieve,j);

end;

procedure FillTotient(i:LongWord); //correct the value of the totient of one number //every prime i at a number that ist multiple of i //therefor k DIV i will always without rest var 

 pTotLst : pLongWord;
 j,k : NativeUint;

Begin 

 pTotLst := @TotientList[0];
 j := i;
 while j <= cLimit do
 Begin
   k:= pTotLst[j];
   k := (k DIV i)*(i-1);
   pTotLst[j]:= k;
   inc(j,i);
 end;

end;

procedure TotientInit(len: NativeUint); var 

 pTotLst : pLongWord;
 pSieve  : pByte;
 i,pr,svLimit : NativeUint;

Begin 

 SieveInit(len);
 T0:= GetTickCount64;
 setlength(TotientList, len+3);
 pTotLst := @TotientList[0];

// Init with the right values for odd and not-odd numbers 

 i := 1;
 repeat
   pTotLst[i] := i;
   pTotLst[i+1] := (i+1) DIV 2;
   inc(i,2);
 until i>len;

 pSieve := @Sieve[0];
 svLimit := High(sieve);
 pr := 1;
 For i := 0 to svlimit do
 begin
   pr := pr+2*pSieve[i];
   FillTotient(pr);
 end;
 T1:= GetTickCount64;
 writeln('totient calculated in ',T1-T0,' ms');

end;

function CheckPerfectTot(n: NativeUint):Boolean; var 

 sum :NativeInt;
 i : NativeUint;

begin 

 i := n;
 sum := n;
 while i >1 do
 begin
   if sum < 0 then
     BREAK;
   i := TotientList[i];//totient(i);
   dec(sum,i);
 end;
 result:= (sum = 0);

end;

var 

 j,k : NativeUint;

Begin 

 TotientInit(climit);
 T0:= GetTickCount64;
 j := 3;
 k := 0;
 repeat
   if CheckPerfectTot(j) then
   Begin
     inc(k);
     if k > 4 then
     Begin
       writeln(j);
       k := 0;
     end
     else
       write(j,',');
   end;
   inc(j,2);
 until j > climit;
 T1:= GetTickCount64;
 writeln;
 WriteLn('testet in ',T1-T0,' ms');

end.</lang>

OutPut
totient calculated in 39474 ms
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
129140163,172186887,236923383,387420489,918330183
1162261467,
testet in 67554 ms

real  1m54,179s -> sieving the primes takes 7151 ms
user  1m53,732s
sys 0m0,447s

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", 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; 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=286862"