Perfect totient numbers: Difference between revisions

{{trans|Python}}

 

R sum((1..n).filter(k -> gcd(@n, k) == 1).map(k -> 1))

 

R r

 

 

{{out}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program totientPerfect64.s */

/***************************************************/

.include "../includeARM64.inc"

<pre>

3 9 15 27 39

</pre>

=={{header|ALGOL 68}}==

# returns the number of integers k where 1 <= k <= n that are mutually prime to n #

PROC totient = ( INT n )INT: # algorithm from the second Go sample #

OD;

print( ( newline ) )

{{out}}

<pre>

 

=={{header|APL}}==

{{out}}

<pre>3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571</pre>

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}

/* ARM assembly Raspberry PI or android with termux */

/* program totientPerfect.s */

/***************************************************/

.include "../affichage.inc"

<pre>

3 9 15 27 39

=={{header|Arturo}}==

{{trans|Nim}}

tt: new n

nn: new n

'x + 2

]

 

{{out}}

 

=={{header|AutoHotkey}}==

 

perfect_totient(n){

tot -= tot / n

return tot

{{out}}

<pre>3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571</pre>

 

=={{header|AWK}}==

# syntax: GAWK -f PERFECT_TOTIENT_NUMBERS.AWK

BEGIN {

return(tot)

}

{{out}}

<pre>

 

=={{header|BASIC}}==

20 N=3

30 S=N: T=0

120 IF T=N THEN PRINT N,: Z=Z+1

130 N=N+2

{{out}}

<pre> 3 9 15 27 39

=={{header|BASIC256}}==

{{trans|FreeBASIC}}

curr = 3

 

next m

return phi

 

 

=={{header|bc}}==

while(j != 0) {

k = j

print "\n"

quit

{{out}}

<pre>

 

=={{header|BCPL}}==

 

let gcd(a,b) = b=0 -> a, gcd(b, a rem b)

$)

wrch('*N')

{{out}}

<pre>3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571</pre>

=={{header|C}}==

Calculates as many perfect Totient numbers as entered on the command line.

#include<stdio.h>

 

return 0;

}

Output for multiple runs, a is the default executable file name produced by GCC

<pre>

 

=={{header|C++}}==

#include <iostream>

#include <vector>

std::cout << '\n';

return 0;

 

{{out}}

</pre>

=={{header|CLU}}==

while b ~= 0 do

a, b := b, a//b

n := n + 2

end

{{out}}

<pre>3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571</pre>

=={{header|Cowgol}}==

 

sub gcd(a: uint16, b: uint16): (r: uint16) is

n := n + 2;

end loop;

{{out}}

<pre>3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571</pre>

 

=={{header|D}}==

import std.numeric;

 

writeln(" ");

}

{{out}}

<pre>

 

=={{header|Dart}}==

 

var cache = List<int>.filled(10000, 0, growable: true);

return n == sum;

}

{{out}}

<pre>

{{libheader| System.SysUtils}}

{{Trans|Go}}

program Perfect_totient_numbers;

 

writeln(']');

readln;

{{out}}

<pre>

 

=={{header|Draco}}==

word c;

while b ~= 0 do

n := n + 2

od

{{out}}

<pre>3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571</pre>

 

=={{header|Factor}}==

math.primes.factors ;

 

 

20 1 lfrom [ perfect? ] lfilter ltake list>array

{{out}}

<pre>

Uses the code from the [[Totient_function#FreeBASIC|Totient Function]] example as an include.

 

 

dim as uinteger found = 0, curr = 3, sum, toti

end if

curr += 1

 

=={{header|Go}}==

 

import "fmt"

fmt.Println("The first 20 perfect totient numbers are:")

fmt.Println(perfect)

 

{{out}}

 

The following much quicker version uses Euler's product formula rather than repeated invocation of the gcd function to calculate the totient:

 

import "fmt"

fmt.Println("The first 20 perfect totient numbers are:")

fmt.Println(perfect)

 

The output is the same as before.

 

=={{header|Haskell}}==

perfectTotients =

filter ((==) <*> (succ . sum . tail . takeWhile (1 /=) . iterate φ)) [2 ..]

 

main :: IO ()

{{Out}}

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

 

=={{header|J}}==

Until =: conjunction def 'u^:(0 -: v)^:_'

Filter =: (#~`)(`:6)

totient_chain =: [: }. (, totient@{:)Until(1={:)

ptnQ =: (= ([: +/ totient_chain))&>

With these definitions I've found the first 28 perfect totient numbers

<pre>

 

=={{header|Java}}==

import java.util.ArrayList;

import java.util.List;

 

}

{{out}}

<pre>

 

=={{header|JavaScript}}==

'use strict';

 

// MAIN ---

main();

{{Out}}

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

One small point of interest in the following implementation is the way the

cacheing of totient values is accomplished using a helper function (`cachephi`).

# jq optimizes the recursive call of _gcd in the following:

def gcd(a;b):

 

"The first 20 perfect totient numbers:",

{{out}}

<pre>

 

=={{header|Julia}}==

 

eulerphi(n) = (r = one(n); for (p,k) in factor(abs(n)) r *= p^(k-1)*(p-1) end; r)

println("The first 20 perfect totient numbers are: $(perfecttotientseries(20))")

println("The first 40 perfect totient numbers are: $(perfecttotientseries(40))")

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

=={{header|Kotlin}}==

{{trans|Go}}

 

fun totient(n: Int): Int {

println("The first 20 perfect totient numbers are:")

println(perfect)

 

{{output}}

 

=={{header|Lua}}==

assert(type(n) == 'number', 'n must be a number!')

local result, i = n, 2

i = i + 1

end

 

{{output}}

 

=={{header|MAD}}==

INTERNAL FUNCTION(Y,Z)

 

VECTOR VALUES FMT = $I9*$

{{out}}

<pre> 3

 

=={{header|Maple}}==

if NumberTheory:-Totient(n) = 1 then

return total + 1;

end if;

end do;

{{output}}

<pre>

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

PerfectTotientNumberQ[n_Integer] := Total[Rest[Most[FixedPointList[EulerPhi, n]]]] == n

res = {};

If[PerfectTotientNumberQ[i], AppendTo[res, i]]

]

{{out}}

<pre>{3,9,15,27,39,81,111,183,243,255,327,363,471,729,2187,2199,3063,4359,4375,5571}</pre>

 

=={{header|Modula-2}}==

FROM InOut IMPORT WriteCard, WriteLn;

 

END;

WriteLn();

{{out}}

<pre> 3 9 15 27 39 81 111 183 243 255 327 363 471 729

 

=={{header|Nim}}==

 

func totient(n: int): int =

inc num

inc n, 2

{{out}}

<pre>

The c-program takes "real 3m12,481s"<BR>

A test with using floating point/SSE is by 2 seconds faster for 46.th perfect totient number, with the coming new Version of Freepascal 3.2.0

{$IFdef FPC}

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

write(Sollist[j],',');

end;

;OutPut:

<pre>compiled with fpc 3.0.4 -O3 "Perftotient.pas"

=={{header|Perl}}==

{{libheader|ntheory}}

 

sub phi_iter {

}

 

{{out}}

<pre>The first twenty Perfect totient numbers:

=={{header|Phix}}==

{{trans|Go}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">totient</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 20 perfect totient numbers are:\n"</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">perfect</span>

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(de gcd (A B)

(until (=0 B)

(inc 'N 2) ) )

(prinl) ) )

{{out}}

<pre>

 

=={{header|PILOT}}==

:n=3

*num

C :n=n+2

J (z<20):*num

{{out}}

<pre>3

 

=={{header|PL/I}}==

gcd: procedure(aa, bb) returns(fixed);

declare (aa, bb, a, b, c) fixed;

end;

end;

{{out}}

<pre> 3 9 15 27 39 81 111 183 243 255

 

=={{header|PL/M}}==

BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;

EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;

END;

CALL EXIT;

{{out}}

<pre>3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571</pre>

 

=={{header|Python}}==

from functools import lru_cache

from itertools import islice, count

 

if __name__ == '__main__':

 

{{out}}

Alternatively, by composition of generic functions:

 

 

from functools import lru_cache

# MAIN ---

if __name__ == '__main__':

{{Out}}

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

<code>totient</code> is defined at [[Totient function#Quackery]].

 

[ dup 1 != while

totient

over size 20 =

until ] drop ] is task ( --> )

 

{{out}}

 

=={{header|Racket}}==

#lang racket

(require math/number-theory)

 

(reverse ns)

 

=={{header|Raku}}==

{{works with|Rakudo|2018.11}}

 

 

my \𝜑 = lazy 0, |(1..*).hyper.map: -> \t { t * [*] t.&prime-factors.squish.map: 1 - 1/* }

my \𝜑𝜑 = Nil, |(3, *+2 … *).grep: -> \p { p == sum 𝜑[p], { 𝜑[$_] } … 1 };

 

{{out}}

<pre>The first twenty Perfect totient numbers:

=={{header|REXX}}==

===unoptimized===

parse arg N . /*obtain optional argument from the CL.*/

if N=='' | N=="," then N= 20 /*Not specified? Then use the default.*/

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*/

{{out|output|text=&nbsp; when using the default input of : &nbsp; &nbsp; <tt> 20 </tt>}}

<pre>

 

('''3²²''' &nbsp; '''=''' &nbsp; '''31,381,059,609''').

parse arg N . /*obtain optional argument from the CL.*/

if N=='' | N=="," then N= 20 /*Not specified? Then use the default.*/

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*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}} <br><br>

 

=={{header|Ring}}==

perfect = []

n = 1

txt = txt + "]"

see txt

<pre>

The first 20 perfect totient numbers are:

 

=={{header|Ruby}}==

 

class Integer

 

puts (1..).lazy.select(&:perfect_totient?).first(20).join(", ")

{{Out}}

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

 

=={{header|Rust}}==

 

static mut CACHE:[i32;10000] = [0; 10000];

println!("{}", " ")

}

{{Out}}

<pre>3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571

 

In this example we define a function which determines whether or not a number is a perfect totient number, then use it to construct a lazily evaluated list which contains all perfect totient numbers. Calculating the first n perfect totient numbers only requires taking the first n elements from the list.

def isPerfectTotient(num: Int): Boolean = LazyList.iterate(totient(num))(totient).takeWhile(_ != 1).foldLeft(0L)(_+_) + 1 == num

def perfectTotients: LazyList[Int] = LazyList.from(3).filter(isPerfectTotient)

//Totient Function

@tailrec def scrub(f: Long, num: Long): Long = if(num%f == 0) scrub(f, num/f) else num

 

{{out}}

 

=={{header|Sidef}}==

func perfect_totient( n, sum=0) { __FUNC__(var(t = n.euler_phi), sum + t) }

 

{{out}}

<pre>

=={{header|Swift}}==

 

var n = n

var i = 2

 

print("The first 20 perfect totient numbers are:")

 

{{out}}

=={{header|Tcl}}==

 

 

set cache(0) 0

}

puts ""

{{out}}

<pre>

{{trans|Go}}

The version using Euler's product formula.

var tot = n

var i = 2

}

System.print("The first 20 perfect totient numbers are:")

 

{{out}}

 

=={{header|zkl}}==

fcn totient(n){ if(phi:=totients[n]) return(phi);

totients[n]=[1..n].reduce('wrap(p,k){ p + (n.gcd(k)==1) })

if(parts==z) z else Void.Skip;

})

{{out}}

<pre>