From 0e58327b195fa4926ba6977f48c7f535ed17d933 Mon Sep 17 00:00:00 2001 From: Adrien Hopkins Date: Mon, 4 Sep 2023 15:29:22 -0500 Subject: Add totative digit count to non-compact output This is done for a few reasons: - Allow the user to easily determine the exact value of the totative ratio - This information is important when the digit map isn't accessible (for radices >36) - More consistency with factors I don't show the exact values of totatives like I do with factors because they're far more common - the superior highly composite (i.e. one of the numbers with the highest factor count) number 720720 has 240 factors and 138240 totatives, for example. --- factors/totative.go | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'factors/totative.go') 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) } -- cgit v1.2.3