From eeff1f3c61fad805bb5ce0170e98378c3b706c18 Mon Sep 17 00:00:00 2001 From: Adrien Hopkins Date: Mon, 9 Oct 2023 13:35:04 -0500 Subject: Add more tests & fix found bugs - TotativeDigits was defined incorrectly, previously counted totatives from 0 to r-1, now counts digits from 1 to r. This ensures that len(TotativeDigits(r)) = Totient(r). --- factors/totative.go | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'factors/totative.go') diff --git a/factors/totative.go b/factors/totative.go index abbbe89..d1947b6 100644 --- a/factors/totative.go +++ b/factors/totative.go @@ -1,7 +1,7 @@ package factors -// Totient calculates the number of numbers less than n that -// are totatives of n (share no factors with n) +// Totient calculates the number of numbers between 1 and n inclusive +// that are totatives of n (share no factors with n) func Totient(n uint) uint { if n == 0 { return 0 @@ -18,12 +18,12 @@ func Totient(n uint) uint { return num * (n / denom) } -// TotativeDigits returns a slice containing every number less than r -// that is a totative of r (shares no factors with r). +// TotativeDigits returns a slice containing every number between 1 and r +// inclusive that is a totative of r (shares no factors with r). func TotativeDigits(r uint32) []uint32 { digits := make([]uint32, Totient(uint(r))) totativesFound := 0 - for d := uint32(0); d < r; d++ { + for d := uint32(1); d <= r; d++ { if gcd(d, r) == 1 { digits[totativesFound] = d totativesFound++ -- cgit v1.2.3