Add tests for properties of many outputs

- Test that every number returned by factors.Factors is actually a
  factor of its argument.
- Test that every number returned by factors.TotativeDigits is actually
  a totative of its argument, and that len(factors.TotativeDigits(r)) ==
  factors.Totient(r).
- Test the properties of factors.Split (regular * totative == digit,
  totative is a totative of radix).

Some of these tests don't test every number in the range, instead
picking randomly, which is done in order to avoid tests taking too long
to execute.  Some testing is better than no testing!

1 files changed, 404 insertions, 0 deletions

diff --git a/factors/table_test.go b/factors/table_test.go
new file mode 100644
index 0000000..ab06aba
--- /dev/null
+++ b/factors/table_test.go
@@ -0,0 +1,404 @@
+package factors
+
+import (
+	"fmt"
+	"maps"
+	"slices"
+	"testing"
+)
+
+// Run a test with a table of cases
+func tableTest[IN comparable, OUT any](t *testing.T, toTest func(IN) OUT,
+	cases map[IN]OUT, equal func(OUT, OUT) bool, name string) {
+	for input, expected := range cases {
+		t.Run(fmt.Sprintf("%v", input), func(t *testing.T) {
+			actual := toTest(input)
+			if !equal(expected, actual) {
+				t.Errorf("%s(%v) = %v, expect %v", name, input, actual, expected)
+			}
+		})
+	}
+}
+
+type uintPair struct{ a, b uint }
+
+var primeFactorCases = map[uint]PrimeFactorization{
+	0:     PrimeFactorization{map[uint]uint{0: 1}},
+	1:     PrimeFactorization{map[uint]uint{}},
+	2:     PrimeFactorization{map[uint]uint{2: 1}},
+	3:     PrimeFactorization{map[uint]uint{3: 1}},
+	4:     PrimeFactorization{map[uint]uint{2: 2}},
+	6:     PrimeFactorization{map[uint]uint{2: 1, 3: 1}},
+	9:     PrimeFactorization{map[uint]uint{3: 2}},
+	10:    PrimeFactorization{map[uint]uint{2: 1, 5: 1}},
+	12:    PrimeFactorization{map[uint]uint{2: 2, 3: 1}},
+	33:    PrimeFactorization{map[uint]uint{3: 1, 11: 1}},
+	60:    PrimeFactorization{map[uint]uint{2: 2, 3: 1, 5: 1}},
+	71:    PrimeFactorization{map[uint]uint{71: 1}},
+	1024:  PrimeFactorization{map[uint]uint{2: 10}},
+	86400: PrimeFactorization{map[uint]uint{2: 7, 3: 3, 5: 2}},
+}
+
+func TestPrimeFactorize(t *testing.T) {
+	equal := func(a, b PrimeFactorization) bool {
+		return maps.Equal(a.exponents, b.exponents)
+	}
+	tableTest(t, PrimeFactorize, primeFactorCases, equal, "PrimeFactorize")
+}
+
+var factorCases = map[uint][]uint{
+	1:  []uint{1},
+	2:  []uint{1, 2},
+	4:  []uint{1, 2, 4},
+	6:  []uint{1, 2, 3, 6},
+	9:  []uint{1, 3, 9},
+	10: []uint{1, 2, 5, 10},
+	12: []uint{1, 2, 3, 4, 6, 12},
+	13: []uint{1, 13},
+	15: []uint{1, 3, 5, 15},
+	16: []uint{1, 2, 4, 8, 16},
+	18: []uint{1, 2, 3, 6, 9, 18},
+	30: []uint{1, 2, 3, 5, 6, 10, 15, 30},
+	32: []uint{1, 2, 4, 8, 16, 32},
+	33: []uint{1, 3, 11, 33},
+	60: []uint{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60},
+	71: []uint{1, 71},
+}
+
+func TestFactors(t *testing.T) {
+	tableTest(t, Factors, factorCases, setEquals, "Factors")
+}
+
+var totativeRatioCases = map[uint]float64{
+	1: 1.0, 2: 0.5, 3: 2.0 / 3.0, 4: 0.5, 6: 1.0 / 3.0, 7: 6.0 / 7.0, 8: 0.5,
+	10: 0.4, 12: 1.0 / 3.0, 14: 3.0 / 7.0, 15: 8.0 / 15.0, 16: 0.5, 20: 0.4,
+	24: 1.0 / 3.0, 30: 4.0 / 15.0, 60: 4.0 / 15.0, 71: 70.0 / 71.0,
+	120: 4.0 / 15.0,
+}
+
+func totativeRatio(n uint) float64 {
+	return float64(Totient(n)) / float64(n)
+}
+
+func TestTotativeRatio(t *testing.T) {
+	tableTest(t, totativeRatio, totativeRatioCases, stdEquals, "TotativeRatio")
+}
+
+var totientCases = map[uint]uint{
+	0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 6: 2, 7: 6, 8: 4, 10: 4, 12: 4,
+	14: 6, 15: 8, 16: 8, 20: 8, 24: 8, 30: 8, 60: 16, 71: 70, 120: 32,
+}
+
+func TestTotativeCount(t *testing.T) {
+	tableTest(t, Totient, totientCases, stdEquals, "Totient")
+}
+
+var totativeDigitCases = map[uint32][]uint32{
+	0:  []uint32{},
+	1:  []uint32{1},
+	2:  []uint32{1},
+	3:  []uint32{1, 2},
+	4:  []uint32{1, 3},
+	6:  []uint32{1, 5},
+	7:  []uint32{1, 2, 3, 4, 5, 6},
+	8:  []uint32{1, 3, 5, 7},
+	10: []uint32{1, 3, 7, 9},
+	12: []uint32{1, 5, 7, 11},
+	14: []uint32{1, 3, 5, 9, 11, 13},
+	15: []uint32{1, 2, 4, 7, 8, 11, 13, 14},
+	16: []uint32{1, 3, 5, 7, 9, 11, 13, 15},
+	20: []uint32{1, 3, 7, 9, 11, 13, 17, 19},
+	24: []uint32{1, 5, 7, 11, 13, 17, 19, 23},
+	30: []uint32{1, 7, 11, 13, 17, 19, 23, 29},
+	60: []uint32{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59},
+	71: []uint32{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, 30,
+		31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
+		46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
+		61, 62, 63, 64, 65, 66, 67, 68, 69, 70},
+	120: []uint32{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59,
+		61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119},
+}
+
+func TestTotativeDigits(t *testing.T) {
+	tableTest(t, TotativeDigits, totativeDigitCases, slices.Equal,
+		"TotativeDigits")
+}
+
+var factorScoreCases = map[uint]float64{
+	1:   1.0,
+	2:   1.5,
+	3:   4.0 / 3.0,
+	4:   1.75,
+	6:   2.0,
+	8:   1.875,
+	10:  1.8,
+	12:  7.0 / 3.0,
+	71:  72.0 / 71.0,
+	120: 3.0,
+	// number that will use bigScore
+	367567200: 62496.0 / 12155.0,
+}
+
+func TestFactorScore(t *testing.T) {
+	// factors.Score is accurate enough that we can test for exact floats!
+	tableTest(t, Score, factorScoreCases, stdEquals, "Score")
+}
+
+var basicRankCases = map[uint]string{
+	// one test per rank, plus three extra (22, 25, 44) to test that
+	// n%3 = 1 vs n%3 = 2 doesn't matter
+	2: "D-", 3: "E-", 4: "C~", 5: "F+", 6: "B~", 7: "F-", 8: "C-",
+	9: "E~", 10: "D+", 11: "F~", 12: "A-", 14: "D~", 15: "E+", 18: "B-",
+	20: "C+", 22: "D-", 24: "A~", 25: "F+", 30: "B+", 44: "C~", 60: "A+",
+	// test that it only depends on n%60
+	62: "D-", 63: "E-", 64: "C~", 65: "F+", 66: "B~", 67: "F-", 68: "C-",
+	69: "E~", 70: "D+", 71: "F~", 72: "A-", 74: "D~", 75: "E+", 78: "B-",
+	80: "C+", 82: "D-", 84: "A~", 85: "F+", 90: "B+", 104: "C~", 120: "A+",
+	// test that it can extend to 0 and 1 as well
+	0: "A+", 1: "F~",
+}
+
+func TestBasicRank(t *testing.T) {
+	tableTest(t, BasicRank, basicRankCases, stdEquals, "BasicRank")
+}
+
+var gcdCases = map[struct{ a, b uint32 }]uint32{
+	{0, 0}: 0, {1, 1}: 1,
+	{0, 1}: 1, {1, 0}: 1,
+	{0, 12}: 12, {12, 0}: 12,
+	{1, 12}: 1, {12, 1}: 1,
+	{6, 10}: 2, {10, 6}: 2,
+	{12, 20}: 4, {20, 12}: 4,
+	{20, 55}: 5, {55, 20}: 5,
+	{60, 120}: 60, {120, 60}: 60,
+	{120, 180}: 60, {180, 120}: 60,
+}
+
+// a version of gcd() for testing purposes
+func gcdTest(c struct{ a, b uint32 }) uint32 {
+	return gcd(c.a, c.b)
+}
+
+func TestGCD(t *testing.T) {
+	tableTest(t, gcdTest, gcdCases, stdEquals, "gcd")
+}
+
+var mtcCases = map[uint32]uint64{
+	2: 0, 3: 0, 4: 2, 5: 10, 6: 8,
+	7: 28, 8: 26, 9: 42, 10: 42, 11: 88, 12: 52,
+	13: 130, 14: 100, 15: 116, 16: 138, 18: 146,
+	20: 190, 24: 252, 28: 416, 30: 380, 32: 618, 36: 598,
+	48: 1100, 60: 1496, 64: 2602, 90: 3662, 120: 6080,
+	210: 18542, 360: 54362, 840: 270122, 2520: 2363528, 5040: 9409112,
+}
+
+func TestMTC(t *testing.T) {
+	tableTest(t, MTC, mtcCases, stdEquals, "MTC")
+}
+
+var sanCases = map[uint]bool{
+	1: true, 2: true, 4: true, 6: true, 12: true, 24: true, 36: true,
+	48: true, 60: true, 120: true, 180: true, 240: true, 360: true,
+	720: true, 840: true, 1260: true, 1680: true, 2520: true, 5040: true,
+	10080: true, 15120: true, 25200: true, 27720: true, 55440: true,
+	3: false, 8: false, 13: false, 18: false, 20: false, 30: false,
+	31: false, 72: false, 107: false, 135: false, 144: false, 300: false,
+	1728: false, 4000: false, 6912: false, 7560: false,
+}
+
+func isSAN(n uint) bool {
+	return Type(n) >= Superabundant
+}
+
+func TestSAN(t *testing.T) {
+	tableTest(t, isSAN, sanCases, stdEquals, "isSAN")
+}
+
+var expOrdCases = map[uint]bool{
+	0: true, 1: true, 2: true, 4: true, 5: false, 6: true, 8: true, 12: true,
+	16: true, 18: false, 20: false, 27: false, 30: true, 36: true, 44: false,
+	60: true, 70: false, 90: false, 96: true, 101: false, 120: true, 144: true,
+	180: true, 770: false, 900: true, 6912: true, 10010: false,
+}
+
+func TestExponentsOrdered(t *testing.T) {
+	tableTest(t, exponentsOrdered, expOrdCases, stdEquals, "exponentsOrdered")
+}
+
+var practicalCases = map[uint]bool{
+	1: true, 2: true, 4: true, 6: true, 8: true, 12: true, 16: true,
+	18: true, 20: true, 24: true, 28: true, 30: true, 32: true, 36: true,
+	48: true, 60: true, 120: true, 180: true, 240: true, 360: true,
+	720: true, 840: true, 1260: true, 1680: true, 2520: true, 5040: true,
+	10080: true, 15120: true, 25200: true, 27720: true, 55440: true,
+	3: false, 10: false, 27: false, 44: false, 45: false, 68: false,
+	70: false, 114: false, 121: false, 770: false, 1729: false, 10010: false,
+}
+
+func TestPractical(t *testing.T) {
+	tableTest(t, practical, practicalCases, stdEquals, "practical")
+}
+
+var typeCases = map[uint]NumberType{
+	2: ColossallyAbundant, 3: NotPractical, 4: Superabundant,
+	6: ColossallyAbundant, 8: OrderedExponent, 10: NotPractical,
+	12: ColossallyAbundant, 18: Practical, 20: Practical, 24: Superabundant,
+	28: Practical, 30: OrderedExponent, 31: NotPractical, 34: NotPractical,
+	60: ColossallyAbundant, 70: NotPractical, 90: Practical, 100: Practical,
+	120: ColossallyAbundant, 144: OrderedExponent, 180: Superabundant,
+	240: Superabundant, 360: ColossallyAbundant, 720: Superabundant,
+	770: NotPractical, 900: OrderedExponent, 1680: Superabundant,
+	1729: NotPractical, 6912: OrderedExponent, 10010: NotPractical,
+	10080: Superabundant, 15120: Superabundant, 25200: Superabundant,
+	27720: Superabundant, 55440: ColossallyAbundant,
+}
+
+func TestType(t *testing.T) {
+	tableTest(t, Type, typeCases, stdEquals, "Type")
+}
+
+// ====== DIGIT MAP TESTS ======
+var (
+	zt = zeroType                      // 00 - zero
+	ot = oneType                       // 0R - one
+	ft = DigitType{1, Regular}         // 1R - factors
+	rt = DigitType{2, Regular}         // 2R - regulars (index 2)
+	wt = DigitType{0, Omega}           // 0ω - omega neighbours
+	at = DigitType{0, Alpha}           // 0α - alpha neighbours
+	nt = DigitType{0, Pseudoneighbour} // 0N - neighbour-like
+	pt = DigitType{0, Opaque}          // 0P - opaque totatives
+)
+var digitMapCases = map[uint][]DigitType{
+	0: []DigitType{},
+	1: []DigitType{zt},
+	2: []DigitType{zt, ot},
+	3: []DigitType{zt, ot, wt},
+	4: []DigitType{zt, ot, ft, wt},
+	5: []DigitType{zt, ot, wt, at, wt},
+	6: []DigitType{zt, ot, ft, ft, rt, wt},
+	8: []DigitType{zt, ot, ft, at, ft, pt, DigitType{1, Alpha}, wt},
+	10: []DigitType{zt, ot, ft, wt, rt, ft, DigitType{1, Omega}, pt,
+		DigitType{3, Regular}, wt},
+	11: []DigitType{zt, ot, wt, at, at, wt, at, pt, nt, pt, wt},
+	12: []DigitType{zt, ot, ft, ft, ft, pt, ft, pt, rt, rt,
+		DigitType{1, Opaque}, wt},
+	16: []DigitType{zt, ot, ft, wt, ft, wt, DigitType{1, Omega}, pt,
+		ft, pt, DigitType{1, Omega}, pt, DigitType{1, Omega},
+		pt, DigitType{1, Opaque}, wt},
+	17: []DigitType{zt, ot, wt, at, wt, pt, at, pt, wt, at,
+		pt, pt, nt, pt, pt, pt, wt},
+	19: []DigitType{zt, ot, wt, wt, at, at, wt, pt, nt, wt,
+		at, pt, nt, pt, pt, nt, pt, pt, wt},
+	22: []DigitType{zt, ot, ft, wt, rt, pt, DigitType{1, Omega}, wt,
+		DigitType{3, Regular}, pt, DigitType{1, Opaque}, ft,
+		DigitType{2, Omega}, pt, DigitType{1, Omega}, pt,
+		DigitType{4, Regular}, pt, DigitType{1, Opaque}, pt,
+		DigitType{2, Opaque}, wt},
+	24: []DigitType{zt, ot, ft, ft, ft, at, ft, pt, ft, rt,
+		DigitType{1, Alpha}, pt, ft, pt, DigitType{1, Opaque},
+		DigitType{1, Alpha}, rt, pt, rt, pt, DigitType{1, Alpha},
+		DigitType{1, Opaque}, DigitType{1, Opaque}, wt},
+}
+
+func TestDigitMap(t *testing.T) {
+	tableTest(t, DigitMap, digitMapCases, slices.Equal, "DigitMap")
+}
+
+// ensures GetDigitType(d, r) == DigitMap(r)[d];
+// does not ensure it has the correct value (that's TestDigitMap's job)
+func TestGetDigitType(t *testing.T) {
+	for radix := range digitMapCases {
+		digitMap := DigitMap(radix)
+		for digit := range digitMap {
+			actual := GetDigitType(uint(digit), radix)
+			if actual != digitMap[digit] {
+				t.Logf("GetDigitType(%d, %d) = %d", digit, radix, actual)
+				t.Errorf("GetDigitType(%d, %d) != DigitMap(%d)[%d]",
+					digit, radix, radix, digit)
+			}
+		}
+	}
+}
+
+// A few test cases related to radix zero
+func TestGetDigitTypeMisc(t *testing.T) {
+	t.Run("GetDigitType(0, 0)", func(t *testing.T) {
+		if GetDigitType(0, 0) != ft {
+			t.Errorf("GetDigitType(0, 0) = %s, expected 1R", GetDigitType(0, 0))
+		}
+	})
+	t.Run("GetDigitType(1, 0)", func(t *testing.T) {
+		if GetDigitType(1, 0) != ot {
+			t.Errorf("GetDigitType(1, 0) = %s, expected 0R", GetDigitType(1, 0))
+		}
+	})
+	t.Run("GetDigitType(2, 0)", func(t *testing.T) {
+		if GetDigitType(2, 0) != pt {
+			t.Errorf("GetDigitType(2, 0) = %s, expected 0P", GetDigitType(2, 0))
+		}
+	})
+}
+
+var splitCases = map[uintPair]uintPair{
+	// digit, radix, regular part, totative part
+	uintPair{0, 0}:    uintPair{0, 1},
+	uintPair{0, 1}:    uintPair{1, 0},
+	uintPair{0, 2}:    uintPair{1, 0},
+	uintPair{0, 12}:   uintPair{1, 0},
+	uintPair{1, 0}:    uintPair{1, 1},
+	uintPair{20, 0}:   uintPair{1, 20},
+	uintPair{360, 0}:  uintPair{1, 360},
+	uintPair{1, 1}:    uintPair{1, 1},
+	uintPair{12, 1}:   uintPair{1, 12},
+	uintPair{87, 1}:   uintPair{1, 87},
+	uintPair{120, 1}:  uintPair{1, 120},
+	uintPair{1, 2}:    uintPair{1, 1},
+	uintPair{1, 3}:    uintPair{1, 1},
+	uintPair{1, 7}:    uintPair{1, 1},
+	uintPair{1, 12}:   uintPair{1, 1},
+	uintPair{1, 39}:   uintPair{1, 1},
+	uintPair{1, 2948}: uintPair{1, 1},
+	uintPair{5, 6}:    uintPair{1, 5},
+	uintPair{10, 6}:   uintPair{2, 5},
+	uintPair{12, 6}:   uintPair{12, 1},
+	uintPair{15, 6}:   uintPair{3, 5},
+	uintPair{35, 6}:   uintPair{1, 35},
+	uintPair{56, 6}:   uintPair{8, 7},
+	uintPair{5, 12}:   uintPair{1, 5},
+	uintPair{10, 12}:  uintPair{2, 5},
+	uintPair{12, 12}:  uintPair{12, 1},
+	uintPair{15, 12}:  uintPair{3, 5},
+	uintPair{35, 12}:  uintPair{1, 35},
+	uintPair{56, 12}:  uintPair{8, 7},
+	uintPair{12, 7}:   uintPair{1, 12},
+	uintPair{56, 7}:   uintPair{7, 8},
+	uintPair{70, 10}:  uintPair{10, 7},
+}
+
+// testing version of Split
+func splitTest(a uintPair) uintPair {
+	regular, totative := Split(a.a, a.b)
+	return uintPair{regular, totative}
+}
+
+func TestSplit(t *testing.T) {
+	tableTest(t, splitTest, splitCases, stdEquals, "Split")
+}
+
+// to be used as the equal paramater for tableTest
+func stdEquals[T comparable](a, b T) bool { return a == b }
+
+func setEquals[E comparable](a, b []E) bool {
+	// use maps to simulate sets
+	// aSet[a] == true means set contains a, false means not
+	aSet := make(map[E]bool)
+	bSet := make(map[E]bool)
+	for _, i := range a {
+		aSet[i] = true
+	}
+	for _, j := range b {
+		bSet[j] = true
+	}
+	return maps.Equal(aSet, bSet)
+}