diff options
Diffstat (limited to 'factors/totative.go')
| -rw-r--r-- | factors/totative.go | 15 |
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) } |
