Perfect totient numbers
Generate and show here, the first twenty Perfect totient numbers.
- Also see
-
- RC task: Totient function
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]
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]