Perfect totient numbers: Difference between revisions
(→{{header|JavaScript}}: Added a first JS draft) |
m (removed one <br> before "Contents") |
||
| Line 9: | Line 9: | ||
;Also see: |
;Also see: |
||
::* the OEIS entry for [http://oeis.org/A082897 perfect totient numbers]. |
::* the OEIS entry for [http://oeis.org/A082897 perfect totient numbers]. |
||
<br |
<br/> |
||
=={{header|C}}== |
=={{header|C}}== |
||
Revision as of 11:57, 10 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]
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)