Perfect totient numbers: Difference between revisions

Content added Content deleted

Inline

@@ Line 78: / Line 78: @@
 [3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571]
 </pre>
+The following much quicker version uses Euler's product formula rather than repeated invocation of the gcd function to calculate the totient:
+<lang go>package main
+import "fmt"
+func totient(n int) int {
+    tot := n
+    for i := 2; i*i <= n; i += 2 {
+        if n%i == 0 {
+            for n%i == 0 {
+                n /= i
+            }
+            tot -= tot / i
+        }
+        if i == 2 {
+            i = 1
+        }
+    }
+    if n > 1 {
+        tot -= tot / n
+    }
+    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>
+The output is the same as before.
 =={{header|Perl 6}}==