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/factors_test.go | 9 +++++++++ factors/totative.go | 15 +++++++++++++-- 2 files changed, 22 insertions(+), 2 deletions(-) (limited to 'factors') 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) } -- cgit v1.2.3