factors/totative.go


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

package factors

// 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)

	for p := range primeFactorization.exponents {
		num *= p - 1
		denom *= p
	}

	return num * (n / denom)
}