/* This script is part of radix_info.
   Copyright (C) 2023  Adrien Hopkins

   This program is free software: you can redistribute it and/or modify
   it under the terms of version 3 of the GNU General Public License
   as published by the Free Software Foundation.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.
*/

package factors

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

	primeFactorization := PrimeFactorize(n)
	num, denom := uint(1), uint(1)

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

	return num * (n / denom)
}

// TotativeDigits returns a slice containing every number between 1 and r
// inclusive that is a totative of r (shares no factors with r).
//
// The returned slice's length is [Totient](r).
func TotativeDigits(r uint32) []uint32 {
	digits := make([]uint32, Totient(uint(r)))
	totativesFound := 0
	for d := uint32(1); d <= r; d++ {
		if gcd(d, r) == 1 {
			digits[totativesFound] = d
			totativesFound++
		}
	}
	return digits
}