package factors

// MTC returns the multiplication table complexity of a radix n.
// This is an estimate of how difficult it is to learn a radix's
// multiplication table.
//
// The MTC is a sum of each digit's row complexity,
// which is the length of the pattern of the product's last digit
// (equal to digit / gcd(digit, radix)).
// Digits 1 and radix - 1 are excluded because they have simpler patterns
// than the other digits.
//
// uint32 is used as the input type and uint64 as the output to prevent
// integer overflow (and because the MTC algorithm is slow).
//
// The MTC of 0 and 1 are both zero.
func MTC(radix uint32) uint64 {
	mtc := uint64(0)
	for digit := uint32(2); digit <= radix-2; digit++ {
		mtc += uint64(radix / gcd(digit, radix))
	}
	return mtc
}

func gcd(a, b uint32) uint32 {
	for b > 0 {
		a, b = b, a%b
	}
	return a
}