From dbd02c8437ae634f4ece3c2979afeb19a3979f61 Mon Sep 17 00:00:00 2001 From: Adrien Hopkins Date: Mon, 9 Oct 2023 15:18:40 -0500 Subject: 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! --- factors/factors_test.go | 404 ----------------------------------------------- factors/property_test.go | 105 ++++++++++++ factors/table_test.go | 404 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 509 insertions(+), 404 deletions(-) delete mode 100644 factors/factors_test.go create mode 100644 factors/property_test.go create mode 100644 factors/table_test.go (limited to 'factors') diff --git a/factors/factors_test.go b/factors/factors_test.go deleted file mode 100644 index ab06aba..0000000 --- a/factors/factors_test.go +++ /dev/null @@ -1,404 +0,0 @@ -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) -} diff --git a/factors/property_test.go b/factors/property_test.go new file mode 100644 index 0000000..7072050 --- /dev/null +++ b/factors/property_test.go @@ -0,0 +1,105 @@ +package factors + +import ( + "fmt" + "math/rand" + "testing" +) + +// TestFactorsDivisible ensures that every number returned by +// Factors is actually a factor of the argument. +func TestFactorsDivisible(t *testing.T) { + for r := uint(1); r < (1 << 16); r++ { + t.Run(fmt.Sprintf("%d", r), func(t *testing.T) { + testFactorsDivisibleOnce(t, r) + }) + } +} + +// One execution of TestFactorsDivisible +func testFactorsDivisibleOnce(t *testing.T, r uint) { + t.Parallel() + factors := Factors(r) + for _, factor := range factors { + if r%factor != 0 { + t.Errorf("%d reported as factor of %d, but not divisible", factor, r) + } + } +} + +// TestTotatives ensures that every number returned by +// TotativeDigits is actually a totative of the argument. +// It also tests that len(TotativeDigits(r)) = Totient(r). +func TestTotatives(t *testing.T) { + for r := uint32(0); r < (1 << 12); r++ { + t.Run(fmt.Sprintf("%d", r), func(t *testing.T) { + testTotativesOnce(t, r) + }) + } +} + +// TestTotativesRandom is like TestTotatives, +// except it randomly chooses radices. +func TestTotativesRandom(t *testing.T) { + for testRun := 0; testRun < 144; testRun++ { + r := uint32(rand.Int31n(1 << 16)) + t.Run(fmt.Sprintf("%d", r), func(t *testing.T) { + testTotativesOnce(t, r) + }) + } +} + +// One execution of TestTotatives +func testTotativesOnce(t *testing.T, r uint32) { + t.Parallel() + totatives := TotativeDigits(r) + for _, totative := range totatives { + if gcd(totative, r) != 1 { + t.Errorf("%d reported as totative of %d, but gcd(%d, %d) = %d", + totative, r, totative, r, gcd(totative, r)) + } + } + + totient := Totient(uint(r)) + if uint(len(totatives)) != totient { + t.Errorf( + "len(TotativeDigits(%d)) = %d, Totient(%d) = %d, should be equal", + r, len(totatives), r, totient) + } +} + +// TestSplitProperties tests Split(digit, radix) to ensure +// totative is a totative and regular * totative = digit. +func TestSplitProperties(t *testing.T) { + for radix := uint(1); radix < 1<<7; radix++ { + for digit := uint(1); digit < 1<<8; digit++ { + t.Run(fmt.Sprintf("radix=%d,digit=%d", radix, digit), + func(t *testing.T) { testSplitOnce(t, digit, radix) }) + } + } +} + +// TestSplitRandom is like TestSplitProperties, +// but with randomly chosen values. +func TestSplitRandom(t *testing.T) { + for i := 0; i < 1728; i++ { + radix := uint(rand.Int31n((1<<15)-1)) + 1 + digit := uint(rand.Int31n((1<<16)-1)) + 1 + t.Run(fmt.Sprintf("radix=%d,digit=%d", radix, digit), + func(t *testing.T) { testSplitOnce(t, digit, radix) }) + } +} + +// One execution of TestSplitProperties +func testSplitOnce(t *testing.T, digit, radix uint) { + t.Parallel() + regular, totative := Split(digit, radix) + if gcd(uint32(totative), uint32(radix)) != 1 { + t.Errorf("Split(%d, %d) = %d, %d; %d not coprime to %d.", + digit, radix, regular, totative, totative, radix) + } + if regular*totative != digit { + t.Errorf("Split(%d, %d) = %d, %d; %d * %d ≠ %d.", + digit, radix, regular, totative, regular, totative, digit) + } +} 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) +} -- cgit v1.2.3