Perfect totient numbers: Difference between revisions
Content added Content deleted
(New draft task with python example.) |
(Added Go) |
||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
Generate and show here, the first twenty [https://en.wikipedia.org/wiki/Perfect_totient_number Perfect totient numbers]. |
Generate and show here, the first twenty [https://en.wikipedia.org/wiki/Perfect_totient_number Perfect totient numbers]. |
||
=={{header|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> |
|||
{{out}} |
|||
<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] |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 22:55, 5 December 2018
Perfect totient numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Generate and show here, the first twenty 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]
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]