diff options
Diffstat (limited to 'factors')
| -rw-r--r-- | factors/factors_test.go | 9 | ||||
| -rw-r--r-- | factors/totative.go | 15 |
2 files changed, 22 insertions, 2 deletions
diff --git a/factors/factors_test.go b/factors/factors_test.go index 8373ede..6b56e25 100644 --- a/factors/factors_test.go +++ b/factors/factors_test.go @@ -71,6 +71,15 @@ func TestTotativeRatio(t *testing.T) { tableTest(t, TotativeRatio, totativeRatioCases, stdEquals, "TotativeRatio") } +var totativeCountCases = map[uint]uint{ + 1: 1, 2: 1, 3: 2, 4: 2, 6: 2, 7: 6, 8: 4, 12: 4, + 14: 6, 15: 8, 30: 8, 60: 16, 120: 32, +} + +func TestTotativeCount(t *testing.T) { + tableTest(t, TotativeCount, totativeCountCases, stdEquals, "TotativeCount") +} + var factorScoreCases = map[uint]float64{ 1: 1.0, 2: 1.5, 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) } |