Perfect totient numbers: Difference between revisions
Content added Content deleted
(Added implementation in D) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 15: | Line 15: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F φ(n) |
||
R sum((1..n).filter(k -> gcd(@n, k) == 1).map(k -> 1)) |
R sum((1..n).filter(k -> gcd(@n, k) == 1).map(k -> 1)) |
||
Line 32: | Line 32: | ||
R r |
R r |
||
print(perfect_totient(20))</ |
print(perfect_totient(20))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 40: | Line 40: | ||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |
||
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }} |
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }} |
||
<syntaxhighlight lang="aarch64 assembly"> |
|||
<lang AArch64 Assembly> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
/* ARM assembly AARCH64 Raspberry PI 3B */ |
||
/* program totientPerfect64.s */ |
/* program totientPerfect64.s */ |
||
Line 166: | Line 166: | ||
/***************************************************/ |
/***************************************************/ |
||
.include "../includeARM64.inc" |
.include "../includeARM64.inc" |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
3 9 15 27 39 |
3 9 15 27 39 |
||
Line 174: | Line 174: | ||
</pre> |
</pre> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find the first 20 perfect totient numbers # |
||
# returns the number of integers k where 1 <= k <= n that are mutually prime to n # |
# 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 # |
PROC totient = ( INT n )INT: # algorithm from the second Go sample # |
||
Line 212: | Line 212: | ||
OD; |
OD; |
||
print( ( newline ) ) |
print( ( newline ) ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 219: | Line 219: | ||
=={{header|APL}}== |
=={{header|APL}}== |
||
< |
<syntaxhighlight lang="apl">(⊢(/⍨)((+/((1+.=⍳∨⊢)∘⊃,⊢)⍣(1=(⊃⊣)))=2∘×)¨)1↓⍳6000</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<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|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}} |
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}} |
||
<syntaxhighlight lang="arm assembly"> |
|||
<lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI or android with termux */ |
/* ARM assembly Raspberry PI or android with termux */ |
||
/* program totientPerfect.s */ |
/* program totientPerfect.s */ |
||
Line 349: | Line 349: | ||
/***************************************************/ |
/***************************************************/ |
||
.include "../affichage.inc" |
.include "../affichage.inc" |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
3 9 15 27 39 |
3 9 15 27 39 |
||
Line 358: | Line 358: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
{{trans|Nim}} |
{{trans|Nim}} |
||
< |
<syntaxhighlight lang="rebol">totient: function [n][ |
||
tt: new n |
tt: new n |
||
nn: new n |
nn: new n |
||
Line 397: | Line 397: | ||
'x + 2 |
'x + 2 |
||
] |
] |
||
print ""</ |
print ""</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 404: | Line 404: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">MsgBox, 262144, , % result := perfect_totient(20) |
||
perfect_totient(n){ |
perfect_totient(n){ |
||
Line 438: | Line 438: | ||
tot -= tot / n |
tot -= tot / n |
||
return tot |
return tot |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<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|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f PERFECT_TOTIENT_NUMBERS.AWK |
# syntax: GAWK -f PERFECT_TOTIENT_NUMBERS.AWK |
||
BEGIN { |
BEGIN { |
||
Line 483: | Line 483: | ||
return(tot) |
return(tot) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 491: | Line 491: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
< |
<syntaxhighlight lang="basic">10 DEFINT A-Z |
||
20 N=3 |
20 N=3 |
||
30 S=N: T=0 |
30 S=N: T=0 |
||
Line 504: | Line 504: | ||
120 IF T=N THEN PRINT N,: Z=Z+1 |
120 IF T=N THEN PRINT N,: Z=Z+1 |
||
130 N=N+2 |
130 N=N+2 |
||
140 IF Z<20 GOTO 30</ |
140 IF Z<20 GOTO 30</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 3 9 15 27 39 |
<pre> 3 9 15 27 39 |
||
Line 513: | Line 513: | ||
=={{header|BASIC256}}== |
=={{header|BASIC256}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
< |
<syntaxhighlight lang="freebasic">found = 0 |
||
curr = 3 |
curr = 3 |
||
Line 544: | Line 544: | ||
next m |
next m |
||
return phi |
return phi |
||
end function</ |
end function</syntaxhighlight> |
||
=={{header|bc}}== |
=={{header|bc}}== |
||
< |
<syntaxhighlight lang="bc">define gcd (i, j) { |
||
while(j != 0) { |
while(j != 0) { |
||
k = j |
k = j |
||
Line 581: | Line 581: | ||
print "\n" |
print "\n" |
||
quit |
quit |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 594: | Line 594: | ||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
< |
<syntaxhighlight lang="bcpl">get "libhdr" |
||
let gcd(a,b) = b=0 -> a, gcd(b, a rem b) |
let gcd(a,b) = b=0 -> a, gcd(b, a rem b) |
||
Line 623: | Line 623: | ||
$) |
$) |
||
wrch('*N') |
wrch('*N') |
||
$)</ |
$)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<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> |
||
Line 629: | Line 629: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Calculates as many perfect Totient numbers as entered on the command line. |
Calculates as many perfect Totient numbers as entered on the command line. |
||
< |
<syntaxhighlight lang="c">#include<stdlib.h> |
||
#include<stdio.h> |
#include<stdio.h> |
||
Line 689: | Line 689: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output for multiple runs, a is the default executable file name produced by GCC |
Output for multiple runs, a is the default executable file name produced by GCC |
||
<pre> |
<pre> |
||
Line 707: | Line 707: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <cassert> |
||
#include <iostream> |
#include <iostream> |
||
#include <vector> |
#include <vector> |
||
Line 758: | Line 758: | ||
std::cout << '\n'; |
std::cout << '\n'; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 766: | Line 766: | ||
</pre> |
</pre> |
||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
< |
<syntaxhighlight lang="clu">gcd = proc (a, b: int) returns (int) |
||
while b ~= 0 do |
while b ~= 0 do |
||
a, b := b, a//b |
a, b := b, a//b |
||
Line 803: | Line 803: | ||
n := n + 2 |
n := n + 2 |
||
end |
end |
||
end start_up</ |
end start_up</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<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|Cowgol}}== |
=={{header|Cowgol}}== |
||
< |
<syntaxhighlight lang="cowgol">include "cowgol.coh"; |
||
sub gcd(a: uint16, b: uint16): (r: uint16) is |
sub gcd(a: uint16, b: uint16): (r: uint16) is |
||
Line 848: | Line 848: | ||
n := n + 2; |
n := n + 2; |
||
end loop; |
end loop; |
||
print_nl();</ |
print_nl();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<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|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">import std.stdio; |
||
import std.numeric; |
import std.numeric; |
||
Line 882: | Line 882: | ||
writeln(" "); |
writeln(" "); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 890: | Line 890: | ||
=={{header|Dart}}== |
=={{header|Dart}}== |
||
< |
<syntaxhighlight lang="dart">import "dart:io"; |
||
var cache = List<int>.filled(10000, 0, growable: true); |
var cache = List<int>.filled(10000, 0, growable: true); |
||
Line 919: | Line 919: | ||
return n == sum; |
return n == sum; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 928: | Line 928: | ||
{{libheader| System.SysUtils}} |
{{libheader| System.SysUtils}} |
||
{{Trans|Go}} |
{{Trans|Go}} |
||
<syntaxhighlight lang="delphi"> |
|||
<lang Delphi> |
|||
program Perfect_totient_numbers; |
program Perfect_totient_numbers; |
||
Line 982: | Line 982: | ||
writeln(']'); |
writeln(']'); |
||
readln; |
readln; |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 989: | Line 989: | ||
=={{header|Draco}}== |
=={{header|Draco}}== |
||
< |
<syntaxhighlight lang="draco">proc nonrec gcd(word a, b) word: |
||
word c; |
word c; |
||
while b ~= 0 do |
while b ~= 0 do |
||
Line 1,031: | Line 1,031: | ||
n := n + 2 |
n := n + 2 |
||
od |
od |
||
corp</ |
corp</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<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|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: formatting kernel lists lists.lazy math |
||
math.primes.factors ; |
math.primes.factors ; |
||
Line 1,044: | Line 1,044: | ||
20 1 lfrom [ perfect? ] lfilter ltake list>array |
20 1 lfrom [ perfect? ] lfilter ltake list>array |
||
"%[%d, %]\n" printf</ |
"%[%d, %]\n" printf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,053: | Line 1,053: | ||
Uses the code from the [[Totient_function#FreeBASIC|Totient Function]] example as an include. |
Uses the code from the [[Totient_function#FreeBASIC|Totient Function]] example as an include. |
||
< |
<syntaxhighlight lang="freebasic">#include"totient.bas" |
||
dim as uinteger found = 0, curr = 3, sum, toti |
dim as uinteger found = 0, curr = 3, sum, toti |
||
Line 1,069: | Line 1,069: | ||
end if |
end if |
||
curr += 1 |
curr += 1 |
||
wend</ |
wend</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,131: | Line 1,131: | ||
fmt.Println("The first 20 perfect totient numbers are:") |
fmt.Println("The first 20 perfect totient numbers are:") |
||
fmt.Println(perfect) |
fmt.Println(perfect) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,140: | Line 1,140: | ||
The following much quicker version uses Euler's product formula rather than repeated invocation of the gcd function to calculate the totient: |
The following much quicker version uses Euler's product formula rather than repeated invocation of the gcd function to calculate the totient: |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,178: | Line 1,178: | ||
fmt.Println("The first 20 perfect totient numbers are:") |
fmt.Println("The first 20 perfect totient numbers are:") |
||
fmt.Println(perfect) |
fmt.Println(perfect) |
||
}</ |
}</syntaxhighlight> |
||
The output is the same as before. |
The output is the same as before. |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">perfectTotients :: [Int] |
||
perfectTotients = |
perfectTotients = |
||
filter ((==) <*> (succ . sum . tail . takeWhile (1 /=) . iterate φ)) [2 ..] |
filter ((==) <*> (succ . sum . tail . takeWhile (1 /=) . iterate φ)) [2 ..] |
||
Line 1,194: | Line 1,194: | ||
main :: IO () |
main :: IO () |
||
main = print $ take 20 perfectTotients</ |
main = print $ take 20 perfectTotients</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<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|J}}== |
=={{header|J}}== |
||
<syntaxhighlight lang="j"> |
|||
<lang J> |
|||
Until =: conjunction def 'u^:(0 -: v)^:_' |
Until =: conjunction def 'u^:(0 -: v)^:_' |
||
Filter =: (#~`)(`:6) |
Filter =: (#~`)(`:6) |
||
Line 1,205: | Line 1,205: | ||
totient_chain =: [: }. (, totient@{:)Until(1={:) |
totient_chain =: [: }. (, totient@{:)Until(1={:) |
||
ptnQ =: (= ([: +/ totient_chain))&> |
ptnQ =: (= ([: +/ totient_chain))&> |
||
</syntaxhighlight> |
|||
</lang> |
|||
With these definitions I've found the first 28 perfect totient numbers |
With these definitions I've found the first 28 perfect totient numbers |
||
<pre> |
<pre> |
||
Line 1,216: | Line 1,216: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
<syntaxhighlight lang="java"> |
|||
<lang Java> |
|||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
import java.util.List; |
import java.util.List; |
||
Line 1,262: | Line 1,262: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,270: | Line 1,270: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,404: | Line 1,404: | ||
// MAIN --- |
// MAIN --- |
||
main(); |
main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<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> |
||
Line 1,415: | Line 1,415: | ||
One small point of interest in the following implementation is the way the |
One small point of interest in the following implementation is the way the |
||
cacheing of totient values is accomplished using a helper function (`cachephi`). |
cacheing of totient values is accomplished using a helper function (`cachephi`). |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
# jq optimizes the recursive call of _gcd in the following: |
# jq optimizes the recursive call of _gcd in the following: |
||
def gcd(a;b): |
def gcd(a;b): |
||
Line 1,450: | Line 1,450: | ||
"The first 20 perfect totient numbers:", |
"The first 20 perfect totient numbers:", |
||
limit(20; perfect_totients)</ |
limit(20; perfect_totients)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,477: | Line 1,477: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
eulerphi(n) = (r = one(n); for (p,k) in factor(abs(n)) r *= p^(k-1)*(p-1) end; r) |
eulerphi(n) = (r = one(n); for (p,k) in factor(abs(n)) r *= p^(k-1)*(p-1) end; r) |
||
Line 1,505: | Line 1,505: | ||
println("The first 20 perfect totient numbers are: $(perfecttotientseries(20))") |
println("The first 20 perfect totient numbers are: $(perfecttotientseries(20))") |
||
println("The first 40 perfect totient numbers are: $(perfecttotientseries(40))") |
println("The first 40 perfect totient numbers are: $(perfecttotientseries(40))") |
||
</ |
</syntaxhighlight>{{output}}<pre> |
||
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 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] |
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] |
||
Line 1,512: | Line 1,512: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="scala">// Version 1.3.21 |
||
fun totient(n: Int): Int { |
fun totient(n: Int): Int { |
||
Line 1,545: | Line 1,545: | ||
println("The first 20 perfect totient numbers are:") |
println("The first 20 perfect totient numbers are:") |
||
println(perfect) |
println(perfect) |
||
}</ |
}</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 1,554: | Line 1,554: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">local function phi(n) |
||
assert(type(n) == 'number', 'n must be a number!') |
assert(type(n) == 'number', 'n must be a number!') |
||
local result, i = n, 2 |
local result, i = n, 2 |
||
Line 1,586: | Line 1,586: | ||
i = i + 1 |
i = i + 1 |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
Line 1,594: | Line 1,594: | ||
=={{header|MAD}}== |
=={{header|MAD}}== |
||
< |
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER |
||
INTERNAL FUNCTION(Y,Z) |
INTERNAL FUNCTION(Y,Z) |
||
Line 1,633: | Line 1,633: | ||
VECTOR VALUES FMT = $I9*$ |
VECTOR VALUES FMT = $I9*$ |
||
END OF PROGRAM </ |
END OF PROGRAM </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 3 |
<pre> 3 |
||
Line 1,657: | Line 1,657: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang="maple">iterated_totient := proc(n::posint, total) |
||
if NumberTheory:-Totient(n) = 1 then |
if NumberTheory:-Totient(n) = 1 then |
||
return total + 1; |
return total + 1; |
||
Line 1,675: | Line 1,675: | ||
end if; |
end if; |
||
end do; |
end do; |
||
num_list;</ |
num_list;</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 1,682: | Line 1,682: | ||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[PerfectTotientNumberQ] |
||
PerfectTotientNumberQ[n_Integer] := Total[Rest[Most[FixedPointList[EulerPhi, n]]]] == n |
PerfectTotientNumberQ[n_Integer] := Total[Rest[Most[FixedPointList[EulerPhi, n]]]] == n |
||
res = {}; |
res = {}; |
||
Line 1,690: | Line 1,690: | ||
If[PerfectTotientNumberQ[i], AppendTo[res, i]] |
If[PerfectTotientNumberQ[i], AppendTo[res, i]] |
||
] |
] |
||
res</ |
res</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<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|Modula-2}}== |
=={{header|Modula-2}}== |
||
< |
<syntaxhighlight lang="modula2">MODULE PerfectTotient; |
||
FROM InOut IMPORT WriteCard, WriteLn; |
FROM InOut IMPORT WriteCard, WriteLn; |
||
Line 1,750: | Line 1,750: | ||
END; |
END; |
||
WriteLn(); |
WriteLn(); |
||
END PerfectTotient.</ |
END PerfectTotient.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 3 9 15 27 39 81 111 183 243 255 327 363 471 729 |
<pre> 3 9 15 27 39 81 111 183 243 255 327 363 471 729 |
||
Line 1,756: | Line 1,756: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import strformat |
||
func totient(n: int): int = |
func totient(n: int): int = |
||
Line 1,787: | Line 1,787: | ||
inc num |
inc num |
||
inc n, 2 |
inc n, 2 |
||
write(stdout, "\n")</ |
write(stdout, "\n")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,802: | Line 1,802: | ||
The c-program takes "real 3m12,481s"<BR> |
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 |
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 |
||
< |
<syntaxhighlight lang="pascal">program Perftotient; |
||
{$IFdef FPC} |
{$IFdef FPC} |
||
{$MODE DELPHI} {$CodeAlign proc=32,loop=1} |
{$MODE DELPHI} {$CodeAlign proc=32,loop=1} |
||
Line 1,958: | Line 1,958: | ||
write(Sollist[j],','); |
write(Sollist[j],','); |
||
end; |
end; |
||
end.</ |
end.</syntaxhighlight> |
||
;OutPut: |
;OutPut: |
||
<pre>compiled with fpc 3.0.4 -O3 "Perftotient.pas" |
<pre>compiled with fpc 3.0.4 -O3 "Perftotient.pas" |
||
Line 1,982: | Line 1,982: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use ntheory qw(euler_phi); |
||
sub phi_iter { |
sub phi_iter { |
||
Line 1,994: | Line 1,994: | ||
} |
} |
||
printf "The first twenty perfect totient numbers:\n%s\n", join ' ', @perfect;</ |
printf "The first twenty perfect totient numbers:\n%s\n", join ' ', @perfect;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first twenty Perfect totient numbers: |
<pre>The first twenty Perfect totient numbers: |
||
Line 2,001: | Line 2,001: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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: #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> |
||
Line 2,037: | Line 2,037: | ||
<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: #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> |
<span style="color: #0000FF;">?</span><span style="color: #000000;">perfect</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,045: | Line 2,045: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(gc 16) |
||
(de gcd (A B) |
(de gcd (A B) |
||
(until (=0 B) |
(until (=0 B) |
||
Line 2,068: | Line 2,068: | ||
(inc 'N 2) ) ) |
(inc 'N 2) ) ) |
||
(prinl) ) ) |
(prinl) ) ) |
||
(totients)</ |
(totients)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,075: | Line 2,075: | ||
=={{header|PILOT}}== |
=={{header|PILOT}}== |
||
< |
<syntaxhighlight lang="pilot">C :z=0 |
||
:n=3 |
:n=3 |
||
*num |
*num |
||
Line 2,101: | Line 2,101: | ||
C :n=n+2 |
C :n=n+2 |
||
J (z<20):*num |
J (z<20):*num |
||
E :</ |
E :</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 |
<pre>3 |
||
Line 2,125: | Line 2,125: | ||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
< |
<syntaxhighlight lang="pli">perfectTotient: procedure options(main); |
||
gcd: procedure(aa, bb) returns(fixed); |
gcd: procedure(aa, bb) returns(fixed); |
||
declare (aa, bb, a, b, c) fixed; |
declare (aa, bb, a, b, c) fixed; |
||
Line 2,167: | Line 2,167: | ||
end; |
end; |
||
end; |
end; |
||
end perfectTotient;</ |
end perfectTotient;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 3 9 15 27 39 81 111 183 243 255 |
<pre> 3 9 15 27 39 81 111 183 243 255 |
||
Line 2,173: | Line 2,173: | ||
=={{header|PL/M}}== |
=={{header|PL/M}}== |
||
< |
<syntaxhighlight lang="plm">100H: |
||
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS; |
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS; |
||
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT; |
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT; |
||
Line 2,231: | Line 2,231: | ||
END; |
END; |
||
CALL EXIT; |
CALL EXIT; |
||
EOF</ |
EOF</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<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|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from math import gcd |
||
from functools import lru_cache |
from functools import lru_cache |
||
from itertools import islice, count |
from itertools import islice, count |
||
Line 2,255: | Line 2,255: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
print(list(islice(perfect_totient(), 20)))</ |
print(list(islice(perfect_totient(), 20)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,263: | Line 2,263: | ||
Alternatively, by composition of generic functions: |
Alternatively, by composition of generic functions: |
||
< |
<syntaxhighlight lang="python">'''Perfect totient numbers''' |
||
from functools import lru_cache |
from functools import lru_cache |
||
Line 2,362: | Line 2,362: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<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> |
||
Line 2,370: | Line 2,370: | ||
<code>totient</code> is defined at [[Totient function#Quackery]]. |
<code>totient</code> is defined at [[Totient function#Quackery]]. |
||
< |
<syntaxhighlight lang="quackery"> [ 0 over |
||
[ dup 1 != while |
[ dup 1 != while |
||
totient |
totient |
||
Line 2,383: | Line 2,383: | ||
over size 20 = |
over size 20 = |
||
until ] drop ] is task ( --> ) |
until ] drop ] is task ( --> ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,390: | Line 2,390: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket |
#lang racket |
||
(require math/number-theory) |
(require math/number-theory) |
||
Line 2,411: | Line 2,411: | ||
(reverse ns) |
(reverse ns) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 2,417: | Line 2,417: | ||
{{works with|Rakudo|2018.11}} |
{{works with|Rakudo|2018.11}} |
||
<lang |
<syntaxhighlight lang="raku" line>use Prime::Factor; |
||
my \𝜑 = lazy 0, |(1..*).hyper.map: -> \t { t * [*] t.&prime-factors.squish.map: 1 - 1/* } |
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 }; |
my \𝜑𝜑 = Nil, |(3, *+2 … *).grep: -> \p { p == sum 𝜑[p], { 𝜑[$_] } … 1 }; |
||
put "The first twenty Perfect totient numbers:\n", 𝜑𝜑[1..20];</ |
put "The first twenty Perfect totient numbers:\n", 𝜑𝜑[1..20];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first twenty Perfect totient numbers: |
<pre>The first twenty Perfect totient numbers: |
||
Line 2,429: | Line 2,429: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===unoptimized=== |
===unoptimized=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates and displays the first N perfect totient numbers. */ |
||
parse arg N . /*obtain optional argument from the CL.*/ |
parse arg N . /*obtain optional argument from the CL.*/ |
||
if N=='' | N=="," then N= 20 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N= 20 /*Not specified? Then use the default.*/ |
||
Line 2,452: | Line 2,452: | ||
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?*/ |
||
#= z==1; do m=1 for z-1; if gcd(m, z)==1 then #= # + 1; end /*m*/ |
#= z==1; do m=1 for z-1; if gcd(m, z)==1 then #= # + 1; end /*m*/ |
||
@.z= #; return # /*use memoization. */</ |
@.z= #; return # /*use memoization. */</syntaxhighlight> |
||
{{out|output|text= when using the default input of : <tt> 20 </tt>}} |
{{out|output|text= when using the default input of : <tt> 20 </tt>}} |
||
<pre> |
<pre> |
||
Line 2,465: | Line 2,465: | ||
('''3<sup>22</sup>''' '''=''' '''31,381,059,609'''). |
('''3<sup>22</sup>''' '''=''' '''31,381,059,609'''). |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates and displays the first N perfect totient numbers. */ |
||
parse arg N . /*obtain optional argument from the CL.*/ |
parse arg N . /*obtain optional argument from the CL.*/ |
||
if N=='' | N=="," then N= 20 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N= 20 /*Not specified? Then use the default.*/ |
||
Line 2,490: | Line 2,490: | ||
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?*/ |
||
#= z==1; do m=1 for z-1; if gcd(m, z)==1 then #= # + 1; end /*m*/ |
#= z==1; do m=1 for z-1; if gcd(m, z)==1 then #= # + 1; end /*m*/ |
||
@.z= #; return # /*use memoization. */</ |
@.z= #; return # /*use memoization. */</syntaxhighlight> |
||
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br> |
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
perfect = [] |
perfect = [] |
||
n = 1 |
n = 1 |
||
Line 2,545: | Line 2,545: | ||
txt = txt + "]" |
txt = txt + "]" |
||
see txt |
see txt |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
The first 20 perfect totient numbers are: |
The first 20 perfect totient numbers are: |
||
Line 2,552: | Line 2,552: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">require "prime" |
||
class Integer |
class Integer |
||
Line 2,572: | Line 2,572: | ||
puts (1..).lazy.select(&:perfect_totient?).first(20).join(", ") |
puts (1..).lazy.select(&:perfect_totient?).first(20).join(", ") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>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 |
||
Line 2,579: | Line 2,579: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">use num::integer::gcd; |
||
static mut CACHE:[i32;10000] = [0; 10000]; |
static mut CACHE:[i32;10000] = [0; 10000]; |
||
Line 2,609: | Line 2,609: | ||
println!("{}", " ") |
println!("{}", " ") |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>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 |
||
Line 2,617: | Line 2,617: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="scala">//List of perfect totients |
||
def isPerfectTotient(num: Int): Boolean = LazyList.iterate(totient(num))(totient).takeWhile(_ != 1).foldLeft(0L)(_+_) + 1 == num |
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) |
def perfectTotients: LazyList[Int] = LazyList.from(3).filter(isPerfectTotient) |
||
Line 2,623: | Line 2,623: | ||
//Totient Function |
//Totient Function |
||
@tailrec def scrub(f: Long, num: Long): Long = if(num%f == 0) scrub(f, num/f) else num |
@tailrec def scrub(f: Long, num: Long): Long = if(num%f == 0) scrub(f, num/f) else num |
||
def totient(num: Long): Long = LazyList.iterate((num, 2: Long, num)){case (ac, i, n) => if(n%i == 0) (ac*(i - 1)/i, i + 1, scrub(i, n)) else (ac, i + 1, n)}.dropWhile(_._3 != 1).head._1</ |
def totient(num: Long): Long = LazyList.iterate((num, 2: Long, num)){case (ac, i, n) => if(n%i == 0) (ac*(i - 1)/i, i + 1, scrub(i, n)) else (ac, i + 1, n)}.dropWhile(_._3 != 1).head._1</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,630: | Line 2,630: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func perfect_totient({.<=1}, sum=0) { sum } |
||
func perfect_totient( n, sum=0) { __FUNC__(var(t = n.euler_phi), sum + t) } |
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))</ |
say (1..Inf -> lazy.grep {|n| perfect_totient(n) == n }.first(20))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,641: | Line 2,641: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">public func totient(n: Int) -> Int { |
||
var n = n |
var n = n |
||
var i = 2 |
var i = 2 |
||
Line 2,696: | Line 2,696: | ||
print("The first 20 perfect totient numbers are:") |
print("The first 20 perfect totient numbers are:") |
||
print(Array(PerfectTotients().prefix(20)))</ |
print(Array(PerfectTotients().prefix(20)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,706: | Line 2,706: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">array set cache {} |
||
set cache(0) 0 |
set cache(0) 0 |
||
Line 2,742: | Line 2,742: | ||
} |
} |
||
puts "" |
puts "" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,756: | Line 2,756: | ||
{{trans|Go}} |
{{trans|Go}} |
||
The version using Euler's product formula. |
The version using Euler's product formula. |
||
< |
<syntaxhighlight lang="ecmascript">var totient = Fn.new { |n| |
||
var tot = n |
var tot = n |
||
var i = 2 |
var i = 2 |
||
Line 2,784: | Line 2,784: | ||
} |
} |
||
System.print("The first 20 perfect totient numbers are:") |
System.print("The first 20 perfect totient numbers are:") |
||
System.print(perfect)</ |
System.print(perfect)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,793: | Line 2,793: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">var totients=List.createLong(10_000,0); // cache |
||
fcn totient(n){ if(phi:=totients[n]) return(phi); |
fcn totient(n){ if(phi:=totients[n]) return(phi); |
||
totients[n]=[1..n].reduce('wrap(p,k){ p + (n.gcd(k)==1) }) |
totients[n]=[1..n].reduce('wrap(p,k){ p + (n.gcd(k)==1) }) |
||
Line 2,803: | Line 2,803: | ||
if(parts==z) z else Void.Skip; |
if(parts==z) z else Void.Skip; |
||
}) |
}) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">perfectTotientW().walk(20).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |