Perfect totient numbers: Difference between revisions
m →{{header|REXX}}: updated to the latest version of the program. |
m →{{header|REXX}}: changed the limit for the program. |
||
Line 118: | Line 118: | ||
<lang rexx>/*REXX program calculates and displays the first N perfect totient numbers. */ |
<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= |
if N=='' | N=="," then N= 20 /*Not specified? Then use the default.*/ |
||
p= 0 /*the count of perfect totient numbers.*/ |
p= 0 /*the count of perfect totient numbers.*/ |
||
@.=. /*memoization array of totient numbers.*/ |
@.=. /*memoization array of totient numbers.*/ |
||
Line 143: | Line 143: | ||
end /*m*/ |
end /*m*/ |
||
@.z= #; return # /*use memoization. */</lang> |
@.z= #; return # /*use memoization. */</lang> |
||
{{out|output|text= when using the default input of : <tt> |
{{out|output|text= when using the default input of : <tt> 20 </tt>}} |
||
<pre> |
<pre> |
||
The first |
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 |
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571 |
||
</pre> |
</pre> |
Revision as of 06:45, 6 December 2018
Generate and show here, the first twenty Perfect totient numbers.
- Related task
- Also see
-
- the OEIS entry for perfect totient numbers.
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]
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 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; #= # + (gcd(m, z)==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]