Perfect totient numbers: Difference between revisions
m (removed one <br> before "Contents") |
(added {{pascal}} an other form to calculate totient) |
||
Line 375: | Line 375: | ||
<pre>[3,9,15,27,39,81,111,183,243,255,327,363,471,729,2187,2199,3063,4359,4375,5571]</pre> |
<pre>[3,9,15,27,39,81,111,183,243,255,327,363,471,729,2187,2199,3063,4359,4375,5571]</pre> |
||
=={{header|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: |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
Revision as of 17:57, 11 December 2018
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
-
- the OEIS entry for perfect totient numbers.
C
Calculates as many number of perfect Totient numbers as entered on the command line. <lang C>#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; } </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
<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
<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)