summaryrefslogtreecommitdiff
path: root/factors/totative.go
diff options
context:
space:
mode:
Diffstat (limited to 'factors/totative.go')
-rw-r--r--factors/totative.go15
1 files changed, 13 insertions, 2 deletions
diff --git a/factors/totative.go b/factors/totative.go
index 3a1f635..7a4bebe 100644
--- a/factors/totative.go
+++ b/factors/totative.go
@@ -1,12 +1,22 @@
package factors
-// TotativeRatio calculates the fraction of numbers less than n that
+// TotativeRatio calculates the fraction of numbers that
// are totatives of n (share no factors with n)
func TotativeRatio(n uint) float64 {
if n == 0 {
panic("0 has no totative ratio!")
}
+ return float64(TotativeCount(n)) / float64(n)
+}
+
+// TotativeCount calculates the number of numbers less than n that
+// are totatives of n (share no factors with n)
+func TotativeCount(n uint) uint {
+ if n == 0 {
+ return 0
+ }
+
primeFactorization := PrimeFactorize(n)
num, denom := uint(1), uint(1)
@@ -14,5 +24,6 @@ func TotativeRatio(n uint) float64 {
num *= p - 1
denom *= p
}
- return float64(num) / float64(denom)
+
+ return num * (n / denom)
}